Given a string of lowercase English alphabets. The task is to check if there exists any subsequence in the string which is not a palindrome. If there is at least 1 subsequence that is not a palindrome then print YES, otherwise print NO.
Examples:
Input : str = "abaab"
Output: YES
Subsequences "ab" or "abaa" or "aab", are not a palindrome.
Input : str = "zzzz"
Output: NO
All possible subsequences are palindrome.
The main observation is that if the string contains at least two distinct characters, then there will always be a subsequence of length at least two which is not a palindrome. Only if all the characters of the string are the same then there will not be any subsequence that is not a palindrome. Because in an optimal way we can choose any two distinct characters from a string and place them in same order one after each to form a non-palindromic string.
Below is the implementation of above approach:
C++
// C++ program to check if there exists // at least 1 sub-sequence in a string // which is not palindrome #include <bits/stdc++.h> using namespace std; // Function to check if there exists // at least 1 sub-sequence in a string // which is not palindrome bool isAnyNotPalindrome(string s) { // use set to count number of // distinct characters set< char > unique; // insert each character in set for ( int i = 0; i < s.length(); i++) unique.insert(s[i]); // If there is more than 1 unique // characters, return true if (unique.size() > 1) return true ; // Else, return false else return false ; } // Driver code int main() { string s = "aaaaab" ; if (isAnyNotPalindrome(s)) cout << "YES" ; else cout << "NO" ; return 0; } |
Java
// Java program to check if there exists // at least 1 sub-sequence in a string // which is not palindrome import java.util.*; class GFG { // Function to check if there exists // at least 1 sub-sequence in a string // which is not palindrome static boolean isAnyNotPalindrome(String s) { // use set to count number of // distinct characters Set<Character> unique= new HashSet<Character>(); // insert each character in set for ( int i = 0 ; i < s.length(); i++) unique.add(s.charAt(i)); // If there is more than 1 unique // characters, return true if (unique.size() > 1 ) return true ; // Else, return false else return false ; } // Driver code public static void main(String []args) { String s = "aaaaab" ; if (isAnyNotPalindrome(s)) System.out.println( "YES" ); else System.out.println( "NO" ); } } |
Python3
# Python3 program to check if there exists # at least 1 sub-sequence in a string # which is not palindrome # Function to check if there exists # at least 1 sub-sequence in a string # which is not palindrome def isAnyNotPalindrome(s): # use set to count number of # distinct characters unique = set () # insert each character in set for i in range ( 0 , len (s)): unique.add(s[i]) # If there is more than 1 unique # characters, return true if ( len (unique) > 1 ): return True # Else, return false else : return False # Driver code if __name__ = = '__main__' : s = "aaaaab" if (isAnyNotPalindrome(s)): print ( "YES" ) else : print ( "NO" ) # This code is contributed by # ihritik |
C#
// C# program to check if there exists // at least 1 sub-sequence in a string // which is not palindrome using System; using System.Collections.Generic; class GFG { // Function to check if there exists // at least 1 sub-sequence in a string // which is not palindrome static bool isAnyNotPalindrome(String s) { // use set to count number of // distinct characters HashSet< char > unique= new HashSet< char >(); // insert each character in set for ( int i = 0; i < s.Length; i++) unique.Add(s[i]); // If there is more than 1 unique // characters, return true if (unique.Count > 1) return true ; // Else, return false else return false ; } // Driver code public static void Main(String []args) { String s = "aaaaab" ; if (isAnyNotPalindrome(s)) Console.WriteLine( "YES" ); else Console.WriteLine( "NO" ); } } // This code contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to check if there exists // at least 1 sub-sequence in a string // which is not palindrome // Function to check if there exists // at least 1 sub-sequence in a string // which is not palindrome function isAnyNotPalindrome(s) { // use set to count number of // distinct characters var unique = new Set(); // insert each character in set for ( var i = 0; i < s.length; i++) unique.add(s[i]); // If there is more than 1 unique // characters, return true if (unique.size > 1) return true ; // Else, return false else return false ; } // Driver code var s = "aaaaab" ; if (isAnyNotPalindrome(s)) document.write( "YES" ); else document.write( "NO" ); </script> |
YES
Complexity Analysis:
- Time Complexity: O(N * logN), where N is the length of the string.
- Auxiliary Space: O(N)
Another approach: Two pointer
Another approach to check if there exists any sub-sequence in a string that is not palindrome is to use the two-pointer technique. We can use two pointers, one pointing to the beginning of the string and the other pointing to the end of the string. We can then move the pointers towards each other until they meet, and check if any non-palindromic sub-sequence exists in the string.
Steps that were to follow the above approach:
- Initialize two pointers, left and right, to the start and end of the string, respectively.
- While left < right, do the following:
- If the character at index left is not equal to the character at index right, then we have found a sub-sequence that is not a palindrome, so return true.
- Otherwise, increment left and decrement right.
- If we have not found any sub-sequence that is not a palindrome, return false.
Below is the code to implement the above steps:
C++
// C++ code to implement the above approach #include <iostream> #include <string> using namespace std; bool hasNonPalindromeSubsequence(string str) { int i = 0, j = str.length() - 1; // move the pointers towards each other until they meet while (i < j) { // if a non-palindromic sub-sequence is found, // return true if (str[i] != str[j]) return true ; i++; j--; } // if no non-palindromic sub-sequence is found, return // false return false ; } // Driver's code int main() { string str = "aaaaab" ; if (hasNonPalindromeSubsequence(str)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
import java.util.*; public class Main { public static boolean hasNonPalindromeSubsequence(String str) { int i = 0 , j = str.length() - 1 ; // move the pointers towards each other until they meet while (i < j) { // if a non-palindromic sub-sequence is found, // return true if (str.charAt(i) != str.charAt(j)) return true ; i++; j--; } // if no non-palindromic sub-sequence is found, return false return false ; } public static void main(String[] args) { String str = "aaaaab" ; if (hasNonPalindromeSubsequence(str)) System.out.println( "Yes" ); else System.out.println( "No" ); } } |
Python3
# Python code for the above approach def hasNonPalindromeSubsequence(string): i = 0 j = len (string) - 1 # Move the pointers towards each other until they meet while i < j: # If a non-palindromic subsequence is found, return True if string[i] ! = string[j]: return True i + = 1 j - = 1 # If no non-palindromic subsequence is found, return False return False # Driver code str = "aaaaab" if hasNonPalindromeSubsequence( str ): print ( "Yes" ) else : print ( "No" ) # THIS CODE IS CONTRIBUTED KIRTI AGARWAL |
C#
// C# code to implement the above approach using System; class GFG { static bool HasNonPalindromeSubsequence( string str) { int i = 0, j = str.Length - 1; // move the pointers towards each other until they meet while (i < j) { // if a non-palindromic sub-sequence is found, // return true if (str[i] != str[j]) return true ; i++; j--; } // if no non-palindromic sub-sequence is found, return // false return false ; } // Driver's code public static void Main() { string str = "aaaaab" ; if (HasNonPalindromeSubsequence(str)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } |
Javascript
function hasNonPalindromeSubsequence(str) { let i = 0; let j = str.length - 1; // Move the pointers towards each other until they meet while (i < j) { // If a non-palindromic subsequence is found, return true if (str[i] !== str[j]) { return true ; } i++; j--; } // If no non-palindromic subsequence is found, return false return false ; } // Driver code const str = 'aaaaab' ; if (hasNonPalindromeSubsequence(str)) { console.log( 'Yes' ); } else { console.log( 'No' ); } |
Yes
Time Complexity: O(N), where N is the length of the string.
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!