C++ Tutorial Quiz - Strings and Arrays - 2020

Strings and arrays are closely related. In some way, a string is really just an array of characters. Lots of string manipulation problems we encounter are therefore based on our understanding of array data types because strings and character arrays are essentially identical in C/C++.

Codes listed here are some solutions to the problems. Some of them could be given as interview questions.

An array is a sequence of variables of the same type arranged contiguously in a block of memory.

Like a linked list, an array provides an essentially linear form of storage, but its properties are significantly different. In a linked list, lookup is always an O(n) operation, but array lookup is O(1) as long as we know the index of the element.

The price for this improved lookup is significantly decreased efficiency in the insertion and deletion of data in the middle of the array. Because an array is essentially a block of memory, it's not possible to create or eliminate storage between any two elements as it is with a linked list. Instead, we must physically move data within the array to make room for an insertion or to close the gap left by a deletion.

Arrays are not dynamic data structures. They have a finite, fixed number of elements. Memory must be allocated for every element in an array. Arrays are best used when we know how many elements we need to store before the program executes. When the program needs a variable amount of storage, the size of the array imposes an arbitrary limit on the amount of data that can be stored. Making the array large enough so that the program always operates below the limit doesn't solve the problem. We could waste memory or we may be short of memory to handle the largest data sizes possible.

Dynamic arrays are arrays that can change size to store as much or as little data as necessary. But it is important to know that most dynamic array implementations use static array internally. A static array cannot be resized, so dynamic arrays are resized by allocating a new array of the appropriate size, copying every element from the old array into the new array, and freeing the old array. This is an expensive operation that must be done as infrequently as possible.

In most cases, an array name is equivalent to a pointer constant (i.e., char *const ptr) to the first element of the array. This means that we can't initialize the element of one array with another array using a simple assignment:

arrayA = arrayB;

This will give us compile error because arrayA is not an lvalue. The assignment is interpreted as an attempt to make arrayA refer to the same area of memory as arrayA. If arrayA has been declared as an array, this causes a compile error bacause we can't change the memory location to which arrayA refers. To copy arrayB to arrayA, we have to write a loop that does an element by element assignment or use a library function such as memcpy() that does the copying for us.

In C/C++, the compiler tracks only the location of arrays, not their size. The programmer is responsible for tracking array sizes, and there is no bounds checking on array accesses. So, the language won't complain if we store something in the twentieth element of a ten-element array. Writing outside of the bounds of an array will probably overwrite some other data structure, leading to all manner of curious and difficult-to-find bugs.

Strings are sequence of characters.

1. C
   A C string is nothing more than a char array. Just as C doesn't track the size of arrays, it doesn't track the size of strings. Instead, the end of the string is marked with a null character, represented in the language as '\0'. The null character is sometimes referred to as NULLCHAR. Using NULL is incorrect because NULL is specifically reserved for use with pointers. The character array must have room for the terminator: A 10-character string requires an 11-character array. This scheme makes finding the length of the string an O(n) operation instead of O(1). So, strlen() must scan through the string until it finds th ends.

   For the same reason that we can't assign one C array to another, we cannot copy C string using = operator. Instead, we generally use the strcpy function.

   It is often convenient to read or alter a string by addressing individual characters of the array. If we change the length of a string in this manner, we should make sure we write a null character after the new last character in the string, and that the character array we are working in is large enough to accommodate the new string and terminator. It's easy to truncate a C string: Just place a null character immediately after the new end of the string.

2. C++
   C-style strings can be used with C++. However, the preferred approach is to use the string class from the standard libraries whenever possible. The string class is a specialization of the basic_string template class using a char data type. If we want to create strings that store Unicode values, we can define a new variant of basic_string based on the wchar_t which is wide character type.
   The string class is very well integrated into the C++ standard libraries. We can use them with streams and iterators. In addition, C++ strings are not null-terminated, so they can store null bytes, unlike C strings. Multiple copies of the same string share the same underlying buffer whenever possible. But because a string is mutable, new buffers are created as necessary.

Codes to find out if a string has all unique characters.

Method A
Using the fact that ASCII characters are treated as an integer. So, we index the 256 array using characters from the string. Each time we indexing the array, we increment the value of that element. The value itself is the counter for that character.

#include <iostream>

using namespace std;

void uniqueCharsA(char *s)
{
	int arr[256]={0};

	while(*s) {
		arr[*s]++ ;
		if(arr[*s] > 1) {
			printf("%c is not unique\n", *s);
			return;
		}
		s++;
	}
	printf("unique\n");
	return ;		
}

int main()
{
	uniqueCharsA("adhijkl");
	uniqueCharsA("adhiiii");
	return 0;
}

Output is:

unique
i is not unique

Method B
Using a bit vector. This is not a universal method. I mean it would only work for certain range of ASCII characters. For example, the characters in the string should be all a-z.
So, in this case, we have only one 32-bit integer to store the characters. But that's enough to store 26 character from a to z.

#include <iostream>
using namespace std;

void uniqueCharsB(char *s)
{
	int bit = 0;

	while(*s) {
		int shift = *s - 'a';
		if(bit & 1 << shift) {
			printf("%c is not unique\n", *s);
			return;
		}
		bit |= 1 << shift;
		s++;
	}
	printf("unique\n");
	return ;	
}

int main()
{
	uniqueCharsB("adhijkl");
	uniqueCharsB("adhiiii");
	return 0;
}

Output is the same as the previous method:

unique
i is not unique

If it's a, the bit vector becomes

0000............001

If the next character is b, the second bit of the bit vector is set to 1

0000............011

If the next character is c, the third bit of the bit vector is turned on

0000............111

So, when we have a character d as the next character, the pattern of the bit vector becomes

0000...........1111

and so on.

As a specific example when the string is "adhiiii", if it's a character d, the bit vector at that point is:

0000000000000000001

since we had a for the previous set of characters. The bit vector will be bit-and (&) with

0000000000000001000

resulting 0, so the while loop continues...

When we see second i of the second input, the bit pattern is

0000......110001001

because we've seen a, d, h, and i already.

It will be Ending with

0000000000100000000

Since we had i before, the i-th bit of the bit vector is on, we have duplicate characters.

Rotating N x N matrix in place.
For example, an image represented by an N X N matrix, where each pixel in the image is 4 bytes. We want to rotate the image by 90 degrees.

#include <iostream>
#include <iomanip>

using namespace std;

const int N = 5;

void makeZero(int a[][N])
{
	int i,layer;
	int first, last;
	int top, topleft;

	for(layer = 0; layer < N/2; layer++) {
		first = layer + 1;
		last = N - 1 - layer;
		
		// edges
		for(i = first; i < last; i++) {
			// saving top  
			top = a[layer][i];		
			// left -> top  
			a[layer][i] = a[N-1-i][layer];
			// bottom -> left  
			a[N-1-i][layer] = a[N-1-layer][N-1-i];
			// right -> bottom  
			a[N-1-layer][N-1-i] = a[i][N-1-layer];
			// saved top -> right  
			a[i][N-1-layer] = top;

		}
		// corners
		topleft = a[layer][layer];
		// lowerleft -> topleft
		a[layer][layer] = a[N-1-layer][layer];
		// bottomright -> lowerleft
		a[N-1-layer][layer] = a[N-1-layer][N-1-layer];
		// topright -> bottomright
		a[N-1-layer][N-1-layer] = a[layer][N-1-layer];
		// topleft ->topright
		a[layer][N-1-layer] = topleft;
	}
}

int main()
{
	int a[5][N]={{1,2,3,4,5},
		     {6,7,8,9,10},
		     {11,12,13,14,15},
		     {16,17,18,19,20},
		     {21,22,23,24,25}};

	/* passing array of N rows */
	makeZero(a);

	for (int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) 
			cout << setw(3) << a[i][j];
		cout << endl;
	}
	return 0;
}

Output is:

 21 16 11  6  1
 22 17 12  7  2
 23 18 13  8  3
 24 19 14  9  4
 25 20 15 10  5

The code below will tell if two strings are anagrams or not. We declare an array bit[256] to set a bit for each ASCII character. Given two strings, one string increases the bit counter and the other decreases an appropriate bit. Then, we check if all the bits are zero. If so, the two are anagrams.

#include <iostream>
using namespace std;

bool anagram(char s1[], char s2[])
{
	int bit[256] = {0};
	if(s1 == NULL || s2 == NULL) return false;

	int len = strlen(s1);
	int len2 = strlen(s2);
	if(len != len2) return false;

	for(int i = 0; i < len; i++) {
		bit[s1[i]]++;
	}

	for(int i = 0; i < len; i++) {
		bit[s2[i]]--;
	}

	for(int i = 0; i < 256; i++) {
		if(bit[i] != 0) return false;
	}
	return true;
}

int main()
{
	char *s1 = "hamlet";
	char *s2 = "letham";
	char *s3 = "latham";

	if(anagram(s1,s2))  
		cout << "Anagram\n";
	else
		cout << "Not an anagram\n";

	if(anagram(s1,s3)) 
		cout << "Anagram\n";
	else
		cout << "Not an anagram\n";
	return 0;
}

Output is:

Anagram
Not an anagram

In this code, we assume we have a dictionary (dict), and get anagrams from it. Each character represents a prime number. We match the smallest prime number with the most frequent alphabet so that the products of characters of a word can be smaller. English alphabet has 26 characters and the 26th prime is 101.

#include <iostream>
#include <map>

using namespace std;

#define NPRIMES 26

// alphabet in the order of frequency
char freq[] =  {'e','a','r','i','o','t','n','s','l','c',
                'u','d','p','m','h','g','b','f','y','w',
                'k','v','x','z','j','q'};

// sample anagrams
char *dict[] = {"acre", "care", "race", "rade", 
                "sender", "enders", "resend", "pender",
                "veto", "vote", "vet" }; 

void setMap(char **dict, int szDict, map<char, int>&primeMap;,  multimap<int, char*>&ana;)
{
    for(int i = 0; i < szDict; i++) {
	cout << "dict[" << i << "]=" << dict[i]<< endl;
        int mult = 1;
        for(int j = 0; j < strlen(dict[i]); j++) 
		mult *= primeMap.find(dict[i][j])->second;
	
        ana.insert(pair<int, char*>(mult,dict[i]));
    }
}

void getPrimes(int a[])
{
    int numberOfPrimes = 0;
    for(int i = 2;i < 200;i++) {
    	int count = 0;
        for(int j = 1;j < i/2+1;j++) 
        	if(i % j == 0) count++;
	if(count == 1) a[numberOfPrimes++] = i;
        if(numberOfPrimes > NPRIMES) break;
    }
}

void reversePrimes(int a[], int sz)
{
    for(int i = 0, j = sz - 1; i <= j; i++, j--) {
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
    }
}

int main()
{
    // get 26 prime numbers 
    int *primes = new int[NPRIMES];
    getPrimes(primes);
    cout << NPRIMES << " prime numbers" << endl;
    for(int i = 0; i < NPRIMES; i++) cout << primes[i] << ",";
    cout << endl;

    // reverse the primes
    reversePrimes(primes, NPRIMES);
    cout << NPRIMES << " prime numbers in reverse" << endl;
    for(int i = 0; i < NPRIMES; i++) cout << primes[i] << ",";
    cout << endl;

    // map char to prime number
    map<char, int> primeMap;
    for(int i = 0; i < NPRIMES; i++) {
		primeMap.insert(pair<char, int>(freq[i], primes[i]));
    }

    int sizeDict = sizeof(dict)/sizeof(dict[0]);
    multimap<int, char*> anagram;
	
    // set mapping
    setMap(dict, sizeDict, primeMap, anagram);

    multimap<int, char*>::const_iterator it;
    for(it = anagram.begin(); it != anagram.end(); ++it) 
		cout << (*it).first << "=>" << (*it).second << endl;

    return 0;
}

Output:

26 prime numbers
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,
26 prime numbers in reverse
101,97,89,83,79,73,71,67,61,59,53,47,43,41,37,31,29,23,19,17,13,11,7,5,3,2,
dict[0]=acre
dict[1]=care
dict[2]=race
dict[3]=rade
dict[4]=sender
dict[5]=enders
dict[6]=resend
dict[7]=pender
dict[8]=veto
dict[9]=vote
dict[10]=vet
81103=>vet
6407137=>veto
6407137=>vote
40980851=>rade
51444047=>acre
51444047=>care
51444047=>race
1121451819=>sender
1121451819=>enders
1121451819=>resend
1424881619=>pender

As we can see from the output, the words that have the same key are the anagrams.

The following example is replacing spaces in a string "Replace spaces with special characters" with "$99"

#include <iostream>
using namespace std;


/* Replacing spaces with "$99" */

char *replacingSpaces(char s[])
{
	if(s == NULL ) return false;

	int i, last = 0, spaceCount = 0;
	char *sp = "$99";

	int lensp = strlen(sp);
	int len = strlen(s);

	for(i = 0; i < len; i++) {
		if(s[i] == ' ') spaceCount++;
	}
	if(spaceCount == 0) return s;

	char *newStr = (char *)malloc(spaceCount*(lensp-1) + len + 1);

	for(i = 0; i < len; i++) {
		if(s[i] != ' ') {
			newStr[last++] = s[i];
		}
		else {
			newStr[last++] = sp[0];
			newStr[last++] = sp[1];
			newStr[last++] = sp[2];
		}
	}
	newStr[last++]='\0';
 
	return newStr;
}

int main()
{
	char s[60] = "Replace spaces with special characters";
	cout << replacingSpaces(s) << endl;
	return 0;
}

Output is:

Replace$99spaces$99with$99special$99characters

A code to remove the duplicate characters in a string without using any additional buffer (no extra copy of the array).

Example A

#include <iostream>
using namespace std;

void removeDuplicateA(char s[])
{
	int i,j,last = 1;
	if(s == NULL) return;
	int len = strlen(s);
	if(len < 2) return;

	for(i = 1; i < len; i++) {
		for(j = 0; j < last; j++) {
			if(s[i] == s[j]) break;
		}
		if(last == j) 
			s[last++] = s[i];
	}
	s[last] = '\0';
}

int main()
{
	const int M = 6;
	char *s[M] = {strdup("abcde"),
		      strdup("aaaaa"),
		      strdup("ababa"),
                      strdup("abcdefabcdefg"),
		      strdup(""),
                      NULL
                      };
	for(int i = 0; i < M; i++) {
		if(s[i])cout << "old: " << s[i] << endl;
		removeDuplicateA(s[i]);
		if(s[i])cout << "new: " << s[i] << endl;
	}
	return 0;
}

Output from the run is:

old: abcde
new: abcde
old: aaaaa
new: a
old: ababa
new: ab
old: abcdefabcdefg
new: abcdefg
old:
new:

Example B

This method requires additional memory, though.

#include <iostream>
using namespace std;

void removeDuplicateB(char s[]) 
{
	int last = 0;
	int c[256]={0};
	if(s == NULL) return;
	if(strlen(s) < 2) return;
	for(int i = 0; i < strlen(s); i++) {
		if(c[s[i]] < 1) {
			c[s[i]]++;
			s[last++] = s[i];
		}	
	}
	s[last]='\0';
}
int main()
{
	const int M = 6;
	char *s[M] = {strdup("abcde"),
		      strdup("aaaaa"),
		      strdup("ababa"),
                      strdup("abcdefabcdefg"),
		      strdup(""),
                      NULL
                      };
	for(int i = 0; i < M; i++) {
		if(s[i])cout << "old: " << s[i] << endl;
		removeDuplicateB(s[i]);
		if(s[i])cout << "new: " << s[i] << endl;
	}

	for(int i = 0; i < M-1; i++) free(s[i]);
	return 0;
}

Output is:

old: abcde
new: abcde
old: aaaaa
new: a
old: ababa
new: ab
old: abcdefabcdefg
new: abcdefg
old:
new:

Given two strings, s1 and s2, this code is checking if s2 is a rotation of s1 using a call to a routine which checks if one word is a substring of another. In this example, strstr() is used.

#include <iostream>
using namespace std;

bool substring(char s1[], char s2[])
{
	bool ret = false;
	if(s1 == NULL || s2 == NULL) return ret;
	if(strlen(s2) == 0) return ret;

  	char *s3 = (char *)malloc(strlen(s1)*2+1);
 	strcpy(s3,s1);
	strcat(s3,s1);

 	if(strstr(s3,s2)) ret = true;
	free(s3);
	return ret;
}

int main()
{
	char *s1 = "apple";
	char *s2 = "leapp";  /* rotation */
	char *s3 = "laepp";  /* not a rotation */
	char *s4 = "pplea";  /* rotation */

	if(substring(s1,s2))  
		cout << "Substring\n";
	else
		cout << "Not a substring\n";

	if(substring(s1,s3))  
		cout << "Substring\n";
	else
		cout << "Not a substring\n";

	if(substring(s1,s4))  
		cout << "Substring\n";
	else
		cout << "Not a substring\n";

	return 0;
}

Output from the run:

Substring
Not a substring
Substring

Write an algorithm such that if an element in an M x N matrix is 0, its entire row and column is set to 0.

#include <iostream>
#include <iomanip>

using namespace std;

const int M = 5, N = 4;

void makeZero(int a[][N])
{
	int row[M] = {0};
	int col[N] = {0};

	for (int i = 0; i < M; i++) {
		for(int j = 0; j < N; j++) {
			if(a[i][j] == 0) {
				row[i] = 1;
				col[j] = 1;
			}
		}
	}

	for (int i = 0; i < M; i++) {
		for(int j = 0; j < N; j++) {
			if(row[i] == 1 || col[j] == 1) {
				a[i][j] = 0;
			}
		}
	}
}

int main()
{
	int a[M][N]={{1,2,3,4},
			{5,6,7,8},
			{9,0,11,12},
			{13,14,15,16},
			{17,18,19,0},
			};
	/* passing array of M rows */
	makeZero(a);

	for (int i = 0; i < M; i++) {
		for(int j = 0; j < N; j++) {
			cout << setw(3) << a[i][j];
		}
		cout << endl;
	}
	return 0;
}

Output from the run:

  1  0  3  0
  5  0  7  0
  0  0  0  0
 13  0 15  0
  0  0  0  0

The code below removes specified characters ("aeiouAEIOU") from a string ("Ludwig Van Beethoven").

#include <iostream>

using namespace std;

void removeChars(char *inStr, char *rmvStr)
{
	int i,j = 0;
	char flag[256] = {0};
	while(*rmvStr) flag[*rmvStr++]++;
	
	for(i = 0; i < strlen(inStr); i++) {
		if(flag[inStr[i]] == 0) {
			inStr[j++] = inStr[i];
		}
	}
	inStr[j] = '\0';
}

int main()
{
	char *input = strdup("Ludwig Van Beethoven");
	char *remove = "aeiouAEIOU";
	cout << "In: " << input << endl;
	cout << "removing " << remove << "..." << endl;
	removeChars(input,remove);
	cout << "Out: " << input << endl;

	return 0;
}

Output is:

In: Ludwig Van Beethoven
removing aeiouAEIOU...
Out: Ldwg Vn Bthvn

The following code reverse words using spaces as delimiters.
First, it reverses all strings.
For example, convert "I am a boy" to "yob a ma I".
Then, we reverse each word one by one. So, the complexity of this algorithm is O(n).

#include <iostream>

using namespace std;

/* reverse the characters in a string */
void reverseString(char *str, int start, int end)
{
	char c;
	for(int i = start, j = end; i <= j; i++, j--) {
		c = str[i];
		str[i] = str[j];
		str[j] = c;	
	}
}

/* reverse the words */
void reverseWords(char *words)
{
	int start = 0, end;

	reverseString(words, 0, strlen(words)-1);
	cout << "Intermediate string: " << words << endl;

	/* find a word using a space as a delimiter, 
	   and reverse it again */
	for(int i = 0; i <= strlen(words); i++) {
		if(words[i] == ' ' || words[i] == '\0') {
			end = i - 1 ;
			reverseString(words, start, end);
			start = i + 1;
		}
	}
}

int main()
{
	char *myStr = strdup("Ludwig Van Beethoven");

	cout << "In: " << myStr << endl;
	reverseWords(myStr);
	cout << "Out: " << myStr << endl;

	free(myStr);

	return 0;
}

Output from the run is:

In: Ludwig Van Beethoven
Intermediate string: nevohteeB naV giwduL
Out: Beethoven Van Ludwig

Q: Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a.

#include <iostream>

using namespace std;

char *fn(char* st1, char* st2)
{
	char *retString = (char*)malloc(strlen(st1));
	char c[256] = {0};
	while(*st2) c[*st2++]++;

	int last = 0;
	while(*st1) {
		if(c[*st1]-- > 0) 
			retString[last++] = *st1;
		st1++;
	}
	retString[last]='\0';
	return retString;
}

int main()
{
	char* a = "stroustrup";
	char* b = "programmings";
	cout << "a = " << a << " b = " << b << endl;
	char *str = fn(a,b);
	cout << "str =" << str << endl;
	free(str);
	return 0;
}

Output is:

a = stroustrup b = programmings
str =srorp

Question: Given a series A,B,C .......Z, AA, AB,AC,AD....AZ,BA,BB...BZ,CA....(Open excel sheet. The names of column represent the series). Given input as number 'n'. Output the 'n' th string of the series. & also vice versa if given string prints its corrsponding string...e.g given AC then its interger is 29 & given 40774 its string value is ABZ..

#include <iostream>

using namespace std;

int columnNumber(char *s)
{
	int base = 26;
	int res = 0;
	int digit = 0;
	for(int i = 0; i < strlen(s); i++) {
		res = res *base + s[i]-'A' + 1 ; 
	}
	return res;
}

void reverse(char *s)
{
	int i,j, temp;
	int len = strlen(s);
	for(i = 0, j = len-1; i < j; i++, j--) {
		temp = s[j];
		s[j] = s[i];
		s[i] = temp;
	}
	s[len] = '\0';
}

void columnLabel(int n, char label[])
{
	int base = 26;
	int digit = 0;
	
	while(n > 0) {	
		label[digit++] = (char)((n-1)%base+'A');
		n = (n-1) / base ;
	}
	label[digit]='\0';
	reverse(label);
}

int main()
{
	char *str ;
	char label[10];
	int n;
	str = "Z";
	cout << str << " = " << columnNumber(str) << endl;
	str = "ZZ";
	cout << str << " = " << columnNumber(str) << endl;
	str = "ZZZ";
	cout << str << " = " << columnNumber(str) << endl;
	str = "ABC";
	cout << str << " = " << columnNumber(str) << endl;

	n = 26;
	columnLabel(n, label);
	cout << n << ": " << label << endl;

	n = 702;
	columnLabel(n, label);
	cout << n << ": " << label << endl;

	n = 18278;
	columnLabel(n, label);
	cout << n << ": " << label << endl;

	n = 731;
	columnLabel(n, label);
	cout << n << ": " << label << endl;

	return 0;
}

Output is:

Z = 26
ZZ = 702
ZZZ = 18278
ABC = 731
26: Z
702: ZZ
18278: ZZZ
731: ABC

Write a function that sums up integers from a text file, one int per line.

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>

using namespace std;

int main() {

	int nn, sum = 0;
	string line;

	ifstream myFile("myInput.txt", ios_base::in); 
	while (getline(myFile,line)) {
		stringstream ss(line);
	 	ss >> nn;
		sum += nn;
	}
	cout << sum << endl;
        return 0;
}

The input file is:

1
2
..
9 
10

Output is the sum of 1,2,....,9,10 which is 55.

Implement a routine that prints all possible ordering of the characters in a string. Treat each character in the input string as a distinct characters, even if it is repeated. In other words, given the string "aaa", the routine should print "aaa" six times.

#include <iostream>
using namespace std;

void swap(char *a, char *b)
{
    char temp;
    temp = *b;
    *b = *a;
    *a = temp;
}

void perm(char *a, int st, int end)
{
    if(st == end) {
	printf("%s\n", a);
    } 
    else {
	for(int i = st; i <= end; i++) {
		swap(a+st, a+i);
		perm(a, st+1, end);
		swap(a+st, a+i);
        }
    }
}

int main()
{
    char s[] = "ABC"; 
    perm(s, 0, strlen(s)-1);
    return 0;
}

Output:

ABC
ACB
BAC
BCA
CBA
CAB

Here is another code for string permute.

#include <iostream>
#include <vector>

using namespace std;

void doPermute(char in[], char out[], vector<bool> used, int length, int level)
{
	if(level == length) {
		cout << out << endl;
		return;
	}
	for(int i = 0; i < length; i++) 
	{
		if(used[i]) continue;
		out[level] = in[i];
		used[i] = true;
		doPermute(in, out, used, length, level+1);
		used[i] = false;
	}
}

void permute(char *s)
{
	int length = strlen(s);
	vector<bool> used(length, false);
	char *out = new char[strlen(s)+1];
	out[length] = '\0';
	int level = 0;
	doPermute(s, out, used, length, level);	
}

int main()
{
    char s[] = "ABC"; 
    permute(s);
    return 0;
}

Output:

ABC
ACB
BAC
BCA
CAB
CBA

Here is much simpler code for string permute.

#include <iostream>
#include <string>

using namespace std;

void permute(string& in, string& out)
{
    if(in.empty()) {
        cout << out << endl;
        return;
    }

    for(int i=0; i < in.size(); ++i) {
        string inNew = in;
        string outNew = out;
	inNew.erase(i,1);
        outNew += in.at(i);
        permute(inNew, outNew);
    } 
}

int main()
{
    string in="ABC";
    string out;  
    permute(in, out);
    return 0;
}

A palindrome is a word or phrase which reads the same in either forward or reverse direction.

1. god / dog
2. gateman / nametag
3. I prefer pi

#include <iostream>
#include <cctype>
using namespace std;

void palindrome(char *s)
{
    int right = strlen(s)-1;
    int left = 0;
    for(int i = 0; i < strlen(s)/2+1; i++) {
        while(s[left] == ' ') left++;
        while(s[right] == ' ') right--;
    	if(tolower(s[left]) != tolower(s[right])) { 
            cout << s << ": not a palindrome" << endl;
            return ;
	}
        else {
            left++;
            right--;
        }
    }
    cout << s << ": a palindrome" << endl;
	return;
}

int main()
{
    char *s = "I prefer pi";
    palindrome(s);
    return 0;
}

Output:

I prefer pi: a palindrome

The following code checks if a string is a palindrome. The comparison starts from both ends using bidirectional iterator:

#include <iostream>
#include <iterator>
#include <string>

using namespace std;

template<typename Bidirectional>
bool isPalindrome(Bidirectional first, Bidirectional last)
{
  while(true)
  {
    last--;

    // when a character is a space, skip it
    if(*last == ' ') last--;
    if(*first == ' ') first++;
    if(first == last)
      break;

    // case insensitive comparison
    if(tolower(*first) != tolower(*last))
      return false;

    first++;

    if(first == last)
      break;
  }
  return true;
}

int main()
{
    string s[] = {"Never odd or even",
                  "No lemon, no melon",
                  "telnet",
                  "reviver"};

    for(int i = 0; i < 4; i++) {
      cout << s[i] << " : "
           << isPalindrome(s[i].begin(), s[i].end()) << endl;
    }

}

Output:

Never odd or even : 1
No lemon, no melon : 1
telnet : 0
reviver : 1

The code below uses two pointers to find the repeated string (O(n^2)).

#include <iostream>
using namespace std;

void find_repeated(char *str)
{
	char *ptr1 = str;
	char *ptr2 = str+1;
	int count;
	int len = strlen(str);
	while(*ptr1) {
		count = 0;
                // ptr1: fixed, while advancing ptr2, compare ptr1+count with ptr2
		while(*ptr2) {
			if(*ptr2 == *(ptr1+count)) {
				count++;
			}
			ptr2++;
		}
                // repeated at least one character
		if(count >= 1) {
			cout << "input=" << str << " Found: " ;
			for(int i = 0; i < count; i++) cout << *(ptr1+i);
			cout << endl;
			return;
		}
		ptr1++;
		ptr2=ptr1+1;			
	}
	cout << "input=" << str << " Not found: " << endl;
	return;
}	

int main()
{    
	char *str1 = "12345234789";
	char *str2 = "1234567890";
	char *str3 = "12345678909";

	find_repeated(str1);
	find_repeated(str2);
	find_repeated(str3);
	
	return 0;
}

Output:

input=12345234789 Found: 234
input=1234567890 Not found:
input=12345678909 Found: 9

For a given array with some of its elements are zero, we want to put all zeros at the end of the array while keeping the relative location of all non-zero elements. In the code below, we count the number of zeros. Move non-zero i-th element into i-count and put zero at i-th array.

#include <iostream>
using namespace std;


int main()
{
    int a[] = {0,1,3,0,8,12,0,4,0,7,0};
    int sz = sizeof(a)/sizeof(int);
    int count = 0;

    for(int i = 0; i < sz; i++)
    {
	if (a[i] == 0) 
	        count++;               
	else if( count > 0 ) {
		a[i - count] = a[i];
		a[i] = 0;
	}
    }
    for(int i = 0; i < sz; i++) cout << a[i] << " ";
    return 0;
}

Output:

1 3 8 12 4 7 0 0 0 0 0

We can have two indices: one for 0 (i) and another one for non-zero (j), and swap the two. The j index is always ahead of i.

#include <iostream>
using namespace std;

void swap(int &a;, int &b;)
{
	int temp = b;
	b = a;
	a= temp;
}

void move_zeros(int a[], int sz)
{
	int i = 0, j = 1;
	while(i  < sz - 2 && j < sz -1) {
	     if(a[i] == 0) {
		 while(!a[j]) j++;
	         swap(a[i], a[j]);
	     }
	     i++; j++;
	}
}

int main()
{
	int a[] = {1, 3, 0, 8, 12, 0, 4, 0, 7};	
	int sz = sizeof(a)/sizeof(a[0]);

	for(int i = 0; i < sz; i++)  cout << a[i] << " ";

	move_zeros(a, sz);

	cout << endl;
	for(int i = 0; i < sz; i++)  cout << a[i] << " ";

	return 0;
}

Complete the function getEqualSumSubstring(), which takes a single argument. The single argument is a string s, which contains only non-zero digits.

This function should print the length of longest contiguous substring of s, such that the length of the substring is 2*N digits and the sum of the leftmost N digits is equal to the sum of the rightmost N digits.If there is no such string, your function should print 0.

Get the sum at each string while moving and compare the sum with the sum that of i/2.

#include <iostream>
using namespace std;

int getEqualSumSubstring(char s[])
{
	int sum1, sum2, found = 0;
	int *sumArray = new int[strlen(s)];
	sumArray[0] = s[0]-'0';
	for(int i = 1; i < strlen(s); i++) {
		sumArray[i] = sumArray[i-1] + s[i]-'0';
		if(i % 2 == 1 && sumArray[i]/2 == sumArray[i/2]) 
			found = i + 1;
	}
	return found;
}


int main()
{
	char *s1 = "12332145";
	char *s2 = "98765432112345678961";
	cout << getEqualSumSubstring(s1) << endl;  // 6
	cout << getEqualSumSubstring(s2) << endl;  // 18
	return 0;
}

Q:Find the largest sum of contiguous sub-array within a one-dimensional array of numbers (Note that the array should contain at least one positive number).

The algorithm has linear complexity.

The following code handles two cases:

1. {-2, 1, -3, 4, -1, 2, 1, -5, 4} - maximum sum = 6
2. {-1, -2, 3, 4, -5, 6} - maximum sum = 8

#include <iostream>
#include <vector>
using namespace std;

int kadane(std::vector<int> const &v;)
{
	int sum_so_far = v[0];  // max sum of subarray
	int max_end= v[0];
	int begin_temp = 0;
	int begin = 0;
	int end = 0;

	for(size_t i = 1; i < v.size(); i++) {
		if(max_end< 0) {
			max_end = v[i];
			begin_temp = i;
		}
		else {
			max_end += v[i];
		}

		if(max_end >= sum_so_far) {
			sum_so_far = max_end;
			begin = begin_temp;
			end = i;
		}
		// cout << v[i] << " max_end=" << max_end << " sum_so_far =" << sum_so_far << endl;
	}
	cout << " begin = " << begin << " end = " << end << endl;
	return  sum_so_far;	
}

int main()
{
    std::vector<int> v = { -2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "Final result A = " << kadane(v) << endl;

    v = { -1, -2, 3, 4, -5, 6};
    cout << "Final result B = " << kadane(v) << endl;
}

1. When the sum of subarray < 0, it resets beginning of the subarray.
2. Otherwise, it sums the subrray.
3. If the sum of subarray is bigger than the sum so far, then it update the sum_so_far with max_end. Also, it marks the max_end with the current index i.

Output:

$ g++ -std=c++11 -o k kadane.cpp
$ ./k
 begin = 3 end = 6
Final result A = 6
 begin = 2 end = 5
Final result B = 8

Here is the table for the case A:

1. Unique Characters
2. Rotating a Matrix by 90 Degrees
3. Are Two Strings Anagram?
4. Get Anagrams from a Dictionary
5. Replacing Spaces of a String
6. Remove Duplicate Strings
7. Rotating String (Substring)
8. Zero Matrix
9. Removing Characters from a String
10. Reverse a String and Words
11. Intersection of Two Character Strings - Filtering
12. Base Conversion
13. String Permutation A
14. String Permutation B
15. String Permutation C
16. String Palindrome
17. Finding repeated string
18. Put zeros to the end of an array
19. getEqualSumSubstring
20. Kadane's algorithm (maximum subarray problem)

Additional codes related to string manipulation are here:

1. int strlen(const char *)
2. char* strcpy(char *, const char*)
3. void * memcpy ( void * destination, const void * source, size_t sz)
4. void *memmove(void *dest, const void *src, size_t sz)
5. void * memset ( void * destination, int source, size_t sz )
6. Converting String to Integer (atoi())
7. Converting Integer to String (itoa())
8. ASCII String to Float - atof()
9. Reversing a String
10. Finding the First Un-repeating (Non-repeating) Character - A
11. Finding the First Un-repeating (Non-repeating) Character - B