Perfect Reversible String

Problem Statement

In the “Perfect Reversible String” problem we have given a string “s”. Check that if reverses of all possible substrings of the input string are present in the string or not. If present it’s a perfectly reversible_string.

Input Format

The first and only one line contain a string “s”.

Output Format

Print “YES” if reverses of all possible substrings of the input string are present in the string. Otherwise, print “NO”.

Example

abc

NO

Explanation: Here total possible substrings are a, b, c, ab, bc, and abc. Here reverse of “ab”, “bc”, and “abc” are not present in the string “abc”.

abba

YES

Explanation: Here total possible substrings are a, b, ab, bb, ba, abb, bba, and abba. Here reverse of all possible substrings are present in “abba”.

Algorithm for Perfect Reversible String

The optimal solution for this problem is based on the fact that the reverse of all substrings of “s” will exist in “s”. If and only if the entire string “s” is a palindrome. We can justify this fact by considering the whole string, a reverse of it will exist only if it is a palindrome. And if a string is a palindrome, then all reverse of all substrings exist.

• Check for the given string for palindrome.
• If the string is palindrome it is perfectly reversible. So, we print “YES”.
• Else print “NO”.

Implementation

C++ Program for Perfect Reversible String

#include <bits/stdc++.h>
using namespace std;

int main()
{
   string s;
   cin>>s;
   int n=s.length();
   int i=0,j=n-1;
   while(i<j)
   {
       if(s[i]!=s[j])
       {
           cout<<"NO"<<endl;
           return 0;
       }
       i++;j--;
   }
   cout<<"YES"<<endl;
   return 0;
}

Java Program for Perfect Reversible String

import java.util.Scanner;

class sum
{
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
        int n=s.length();
        int i=0,j=n-1,flag=0;
        while(i<j)
        {
            if(s.charAt(i)!=s.charAt(j))
            {
                flag=1;
                i=j;
            }
            i++;j--;
        }
        if(flag==1)
        {
            System.out.println("NO");
        }
        else
        {
            System.out.println("YES");
        }
    }
}

racecar

YES

Complexity Analysis for Perfect Reversible String

Time Complexity

O(n) where n is the size of the given string “s”. Here we simply check the character from the beginning and end of the string. If char is not same print “NO”, otherwise increase beginning by one and decrease end by one. If we visit all the char successfully then we print “YES”.

Space Complexity

O(1) because we don’t create an auxiliary space here. Simply check the conditions and print the answer.