Site icon Study Algorithms

Given an array of characters formed with a’s and b’s. The center is marked with ‘ X ‘. Check whether the string is palindrome or not?

Question: Given an array of characters formed by a’s and b’s. The string is marked with special character ‘X’ which represents the middle of the list (for example ababa…ababXbabab…baaa). Check whether the string is palindrome or not?

Input: ababXbaba
Output: PALINDROME

Input: ababababababbbbbXbbbbabababababa
Output: PALINDROME

Input: abababbbabbXabbbabbabbb
Output: NOT PALINDROME

This is one of the simplest algorithms. What we do is, start two indexes – one at the beginning of the string and other at the ending of the string. Each time compare whether the values at both the indexes are same or not. If the values are not same then we say that the given string is not a palindrome and break the loop. If the values are same then increment the starting index and decrement the ending index. Continue this process until both the indexes meet at the middle (at X) [this means that it is a palindrome].

If the indexes fail to meet, that means that the string is not a palindrome.

//function to check if the string is Palindrome
int isPalindrome(char *str)
{
	//the first index
	int start_index = 0;

	//the last index
	int last_index = strlen(str);

	while(start_index < last_index && str[start_index] == str[last_index])
	{
		//increment start index and decrement last index
		start_index++;
		last_index--;
	}

	if(start_index < last_index)
	{
		//this means that we did not reach the center
		printf("NOT A PALINDROME");
		return 0;
	}
	else
	{
		//we reached the center
		printf("PALINDROME");
		return 1;
	}
}

You can download a working sample of the source code here. Open in your favorite editor like gEdit, Notepad++, vim etc…

Exit mobile version