August 10, 2010

String repeated characters count

By Mohammed Abualrob Algorithms and Data Structures 2 Comments

Problem

Write a C++ function to check string for repeated characters.

Algorithm

Using brute force we can start with the first character then compare it to the rest of the characters. If we can find a match then the string does have repeated characters otherwise we move to the next character and so on. If we finish all characters without finding a match then the string does not have repeated characters.

Code

Here is the brute force code

//Includes
#include <iostream>

//STD
using namespace std;

//Receives input string and size
int BruteRepeated(char* str, int n)
{
	//Loop in the string character by character
	for (int i = 0; i < n; i++)
	{
		//Compare each character to the rest of
		//the characters
		for (int j = i + 1; j < n; j++)
		{
			//return true
			if (str[i] == str[j]) return 1;
		}
	}

	//No match return false
	return 0;
}

//Main function
void main()
{
	//Sample string
	char str[] = "abcdefghijklmnopqrstuvwxyza";

	//Check string
	if (BruteRepeated(str, 27))
	{
		cout << "Contains repeated characters" << endl;
	}
	else
	{
		cout << "does not Contain repeated characters" << endl;
	}
}

//Includes

#include <iostream>

//STD

using namespace std;

//Receives input string and size

int BruteRepeated(char* str, int n)

{

//Loop in the string character by character

for (int i = 0; i < n; i++)

{

//Compare each character to the rest of

//the characters

for (int j = i + 1; j < n; j++)

{

//return true

if (str[i] == str[j]) return 1;

}

//No match return false

return 0;

}

//Main function

void main()

{

//Sample string

char str[] = "abcdefghijklmnopqrstuvwxyza";

//Check string

if (BruteRepeated(str, 27))

{

cout << "Contains repeated characters" << endl;

}

else

{

cout << "does not Contain repeated characters" << endl;

}

Solution

Another solution is to sort the string then loop through the string character by character and check for duplicates. We can borrow the merge sort code to sort the string (nlogn). Once the string is sorted we can check for duplicates in linear time.

Code

Here is the code to do that

//Includes
#include <iostream>

//STD
using namespace std;

//Receives input string and size
char* Sort(char* str, int n)
{
	//If the string is only one
	//character then it is already
	//sorted
	if (n == 1)
	{
		return str;
	}
	else
	{
		//Calculate the middle
		int m = n/2;

		//Allocate space for the two halves
		char* a = new char[m];
		char* b = new char[n-m];

		//Copy the first half of the string to a
		//and the second half of the string to b
		for (int i = 0; i < m; i++) a[i] = str[i];
		for (int i = m; i < n; i++) b[i-m] = str[i];

		//Recursively call the function on the two
		//halves
		a = Sort(a, m);
		b = Sort(b, n-m);

		//The rest of the code is to merge the sorted
		//halves
		int l = 0;
		int r = 0;
		int k = 0;

		while (l < m && r < n-m)
		{
			//If the character from the first half
			//is less than the character of the
			//second half then push it to the result
			if (a[l] <= b[r])
			{
				str[k] = a[l];
				l++;
			}
			//Otherwise push the character from the
			//second half
			else
			{
				str[k] = b[r];
				r++;
			}

			k++;
		}

		//If the loop above is finished and still
		//l is less than m then this means there
		//are characters in the first half that
		//need to be appended to the result
		if (l < m)
		{
			while (l < m)
			{
				str[k] = a[l];
				l++;
				k++;
			}
		}

		//Similarly we need to append those characters
		//in the second half that were not added
		if (r < n-m)
		{
			while( r < n-m)
			{
				str[k] = b[r];
				r++;
				k++;
			}
		}

		//Return the sorted string
		return str;
	}
}

//Receives input string and size
int SortRepeated(char* str, int n)
{
	//Sort string
	str = Sort(str, n);

	//Check for duplicates
	for (int i = 0; i < n - 1; i++)
	{
		//If there is a duplicate then return true
		if (str[i] == str[i + 1]) return 1;
	}

	//No match return false
	return 0;
}

//Main function
void main()
{
	//Sample string
	char str[] = "abcdefghijklmnopqrstuvwxyza";

	//Check string
	if (SortRepeated(str, 27))
	{
		cout << "Contains repeated characters" << endl;
	}
	else
	{
		cout << "does not Contain repeated characters" << endl;
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

//Includes

#include <iostream>

//STD

using namespace std;

//Receives input string and size

char* Sort(char* str, int n)

{

//If the string is only one

//character then it is already

//sorted

if (n == 1)

{

return str;

}

else

{

//Calculate the middle

int m = n/2;

//Allocate space for the two halves

char* a = new char[m];

char* b = new char[n-m];

//Copy the first half of the string to a

//and the second half of the string to b

for (int i = 0; i < m; i++) a[i] = str[i];

for (int i = m; i < n; i++) b[i-m] = str[i];

//Recursively call the function on the two

//halves

a = Sort(a, m);

b = Sort(b, n-m);

//The rest of the code is to merge the sorted

//halves

int l = 0;

int r = 0;

int k = 0;

while (l < m && r < n-m)

{

//If the character from the first half

//is less than the character of the

//second half then push it to the result

if (a[l] <= b[r])

{

str[k] = a[l];

l++;

}

//Otherwise push the character from the

//second half

else

{

str[k] = b[r];

r++;

}

k++;

}

//If the loop above is finished and still

//l is less than m then this means there

//are characters in the first half that

//need to be appended to the result

if (l < m)

{

while (l < m)

{

str[k] = a[l];

l++;

k++;

}

//Similarly we need to append those characters

//in the second half that were not added

if (r < n-m)

{

while( r < n-m)

{

str[k] = b[r];

r++;

k++;

}

//Return the sorted string

return str;

}

//Receives input string and size

int SortRepeated(char* str, int n)

{

//Sort string

str = Sort(str, n);

//Check for duplicates

for (int i = 0; i < n - 1; i++)

{

//If there is a duplicate then return true

if (str[i] == str[i + 1]) return 1;

}

//No match return false

return 0;

}

//Main function

void main()

{

//Sample string

char str[] = "abcdefghijklmnopqrstuvwxyza";

//Check string

if (SortRepeated(str, 27))

{

cout << "Contains repeated characters" << endl;

}

else

{

cout << "does not Contain repeated characters" << endl;

}

Solution

Another solution is to calculate character counts. If there is a character with a count greater than one then the string contains repeated characters. An efficient way to calculate character counts is achieved by using hash tables. You can refer to the following post for more details.

Thanks for visiting. Please use the comments section below for feedback.

8 BIT AVENUE

String repeated characters count

More from my site

About Author

Mohammed Abualrob

Add a Comment