String Manipulation Problems

1.Divide a string in n equal parts
http://www.geeksforgeeks.org/divide-a-string-in-n-equal-parts/

2.Remove Spaces / Trim a string
http://www.geeksforgeeks.org/remove-spaces-from-a-given-string/

Variation 1:
Remove multiple spaces from a string and keep only 1 space in between two words.You are also required to remove leading and trailing spaces in order to make a sentence.
http://www.geeksforgeeks.org/remove-extra-spaces-string/

3.atoi() and itoa()
http://www.geeksforgeeks.org/write-your-own-atoi/
http://www.geeksforgeeks.org/implement-itoa/

4.String Text Justification
http://www.programcreek.com/2014/05/leetcode-text-justification-java/

5.Escape all % characters in a string; % is the escape character
Example :
Input : India has GDP of 10% in 2009
Output : Input has GDP of 10%% in 2009
Strategy:

It is usually not be possible to do this in-place since the original unescaped string may not have enough space in the array to store the additional escape characters. But if we create a new array, O(n) algo is possible, though space complexity will increase.

String escapePercent(String input) {
    StringBuilder sb = new StringBuilder();
    char[] str = input.toCharArray();

    for (int i = 0; i < input.length(); i++) {
        if (str[i] == ‘%’) sb.append(‘%’);
        sb.append(str[i]);
    }

    return new String(sb);
}

6. Remove duplicates from a string
Variation 1 http://www.geeksforgeeks.org/recursively-remove-adjacent-duplicates-given-string/
Variation 2 http://www.geeksforgeeks.org/remove-all-duplicates-from-the-input-string/
Variation 3 Write a function that deletes consecutive identical character sets of size 1, 2, 3. For example if aabbabc is given as input after first iteration, it should be ababc and after that it should become abc. if aabbcabc is given it should give abcabc after first interation, no change in second iteration and abc after third iteration.
Variation 4 http://www.geeksforgeeks.org/check-string-can-become-empty-recursively-deleting-given-sub-string/
Variation 3 Solution
The approach is based on Sliding window approach where in a window, the first & last characters are being compared.
#include <stdio.h>
#include <string.h>

void rem(char *str,int N,int k)
{
        int low,high,i,j,L;

        for(L=1;L<=k;L++)
        {
                i=L;j=L;
                while(i<N)
                {
                        low=i-L;high=i;
                        if(low>=0)
                        {
                                if(str[low]!=str[high])
                                        str[j++]=str[i];
                        }
                        i++;
                }
                str[j]='\0';
                N=j;
                printf("%s\n\n",str);
        }
       
}

int main()
{
        char str[]="abcabcabcabc",k=3;
        rem(str,strlen(str),k);
        return 0;
}

The above algo can be further simplified.

void rem(char *str,int N,int k)
{
        int low,high,i,j,len,top;

        for(len = 1; len <= k; ++len)
        {
                top  = len;
                for(low = 0,high = low+len; high < N; ++high,++low)
                {
                        if(str[high] && str[low] != str[high])
                                str[top++] = str[high];
                }
                str[top++] = '\0';
                N = top;
                printf("%s\n",str);
        }

}

7. Remove specified characters from a string
You are given 2 strings. The first string is the input string that needs to be cleaned (in place) and the second string contains characters that need to be removed from the the first string. For example if string1 = "teetotaller" and removeString= "ae" then the output (cleaned string) will look like "ttotllr".

Strategy:

• Loop through individual characters of string1 and check if they exist in the removeString.
• Copy a character back to the input string only if it doesn't exist in removeString.
• Terminate the string with a NULLCHAR ('\0').

Code:

#include<stdio.h>
#include<string.h>

int main()
{ 
char str[]="teeetotalleer";
char toremove[]="aae";
int i=0,j=0;
int flag[256]={0};

while(toremove[i]!='\0')
   {flag[toremove[i]]++;
   i++;}
   
i=0;
while(str[i]!='\0')
   { 
    if(flag[str[i]]==0)
       str[j++]=str[i];
    i++;
   }
str[j]='\0';      
printf("\n%s",str);
getchar();
return 0;

} 

//Removes the specified characters from an input string
void RemoveCharacters(char str[], char remove[])
{
int strLen = strlen(str);
int removeStrLen = strlen(remove);

bool removeCharacterFlags[128] = {false}; // assume ASCII character set

// set the flag for characters present in the remove string
for(int i=0; i<removeStrLen; i++)
{
    removeCharacterFlags[remove[i]] = true;
}

int destIndex = 0;      // index within the input string where the next
                        // clean character will go.
for(int i=0; i<strLen; i++)
{
    if(!removeCharacterFlags[str[i]])
    {
        str[destIndex++] = str[i];
    }
}
str[destIndex] = '\0';
}