Online Algorithm for Checking Palindrome in a Stream


Difficulty Level Medium
Frequently asked in Accolite Adobe Zenefits
Palindrome Pattern Searching String

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.