Table of Contents
Problem Statement
In the “Online Algorithm for Checking Palindrome in a Stream” problem, we have given a stream of characters(charcaters are received one by one). Write a program that will print ‘yes’ every time if the received characters till now form a palindrome.
Input Format
The first and only one line containing a string s.
Output Format
Traverse character by character and Print “YES” if the current string(formed by all char till this char) is a palindrome else print “NO”.
Constraints
- 1<=|s|<=10^5
- s[i] must be a lower case English alphabet
Example
bcdcb
YES NO NO NO YES
Explanation: For i=0, print YES because “b” is a palindrome. If i=1, print NO because “bc” is not a palindrome. For i=2, print NO because “bcd” is not a palindrome. If, i=3, print NO because “bcdc” is not a palindrome. And for i=4, print YES because “bcdcb” is a palindrome.
Approach for Online Algorithm for Checking Palindrome in a Stream
The basic idea is that for every character in the input string, check whether s[0..i] is a palindrome or not. In another method(optimal), the main idea is to use the idea of the Rolling hash used in the Rabin Karp algorithm as the next hash value can be calculated from the previous in O(1) time. Keep track of reverse of first half and second half for every index
Algorithm
1. The first character is always a palindrome, so print yes for the first character.
2. Initialize reverse of the first half to the first character and second half to the second character. Let the hash value of the first half reverse be ‘FR’ and that of the second-half be ‘S’.
3. Traverse the string from the second character
- If ‘FR’ and ‘S’ are the same, then check iff s[0..i] is a palindrome using a simple character by character match
- Update ‘FR’ and ‘S’ for the next iteration.
- If ‘i’ is even, then add the next character to the beginning of ‘FR’ and end of the second half and update hash values.
- If ‘i’ is odd, then keep ‘FR’ as it is, removes the leading character from the second, and append the next character at the end.
Working implementation of the above algorithm
s = “bcdcb”
Initialize FR and S. FR = hash(“b”), S = hash(“c”)
Traverse from the second character
i = 1, FR and S are not equal, so print NO.
update FR and S, i is odd so FR will not be changed and S becomes hash(“d”)
i = 2, FR and S are not equal, so print NO.
update FR and S, i is even so FR becomes hash(“cb”) and S becomes hash(“dc”)
i = 3, FR and S are not equal, so print NO.
update FR and S, i is odd so FR will not be changed and S becomes hash(“cb”)
i = 4, FR and S are matched, so print YES.
No need to update, as it is the last index
Implementation
C++ Program for Online Algorithm for Checking Palindrome in a Stream
#include <bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
// p is a prime number used for evaluating Rabin Karp's Rolling hash
#define p 103
void isPalindrome(string s)
{
// Length of input string
int N = s.length();
// first character is a palindrome
cout<<"YES"<<endl;
// Return if string has only one character
if (N == 1) return;
// Initialize first half reverse and S half for
// as FR and S characters
int FR = s[0] % p;
int S = s[1] % p;
int h = 1, i, j;
// Now check for palindromes from S character
// onward
for (i=1; i<N; i++)
{
// If the hash values of 'FR' and 'S'
// match, then only check individual characters
if (FR == S)
{
//check if s[0..i] is a palindorme
for (j = 0; j < i/2; j++)
{
if (s[j] != s[i-j])
break;
}
if((j == i/2))
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
else
{
cout<<"NO"<<endl;
}
//update hash values
if (i != N-1)
{
// If i is even (next i is odd)
if (i%2 == 0)
{
// Add next character after first half at beginning
// of 'FR'
h = (h*NO_OF_CHARS) % p;
FR = (FR + h*s[i/2])%p;
// Add next character after S half at the end
// of S half.
S = (S*NO_OF_CHARS + s[i+1])%p;
}
else
{
// If i is odd (next i is even) then we
// need not update FR, we need to remove
// first character of S and append a
// character to it.
S = (NO_OF_CHARS*(S + p - s[(i+1)/2]*h)%p
+ s[i+1])%p;
}
}
}
}
int main()
{
string s;
cin>>s;
isPalindrome(s);
return 0;
}
Java Program for Online Algorithm for Checking Palindrome in a Stream
import java.util.Scanner;
class sum
{
private static int p=103;
private static int NO_OF_CHARS = 256;
public static void isPalindrome(String s)
{
// Length of input string
int N = s.length();
// first character is a palindrome
System.out.println("YES");
// Return if string has only one character
if (N == 1) return;
// Initialize first half reverse and S half for
// as FR and S characters
int FR = s.charAt(0) % p;
int S = s.charAt(1) % p;
int h = 1, i, j;
// Now check for palindromes from S character
// onward
for (i=1; i<N; i++)
{
// If the hash values of 'FR' and 'S'
// match, then only check individual characters
if (FR == S)
{
//check if s[0..i] is a palindorme
for (j = 0; j < i/2; j++)
{
if (s.charAt(j) != s.charAt(i-j))
break;
}
if((j == i/2))
{
System.out.println("YES");
}
else
{
System.out.println("NO");
}
}
else
{
System.out.println("NO");
}
//update hash values
if (i != N-1)
{
// If i is even (next i is odd)
if (i%2 == 0)
{
// Add next character after first half at beginning
// of 'FR'
h = (h*NO_OF_CHARS) % p;
FR = (FR + h*s.charAt(i/2))%p;
// Add next character after S half at the end
// of S half.
S = (S*NO_OF_CHARS + s.charAt(i+1))%p;
}
else
{
// If i is odd (next i is even) then we
// need not update FR, we need to remove
// first character of S and append a
// character to it.
S = (NO_OF_CHARS*(S + p - s.charAt((i+1)/2)*h)%p
+ s.charAt(i+1))%p;
}
}
}
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
String s = sr.next();
isPalindrome(s);
}
}abacbca
YES NO YES NO NO NO NO
Complexity Analysis for Online Algorithm for Checking Palindrome in a Stream
Time Complexity
O(n*n) where n is the size of the given string. Here n*n is the worst-case time complexity. But in general, it works much better than the basic simple approach. As we avoid complete substring comparison most of the time by first comparing hash values. The worst-case occurs for input strings with all same characters like “zzzzzzzzz”.
Space Complexity
O(1) because we don’t any auxiliary space at here.