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.