Given a string str[] of N lower case English alphabets, the task is to check if there exists a substring of the given string such that the substring is composed of only two characters and the frequency of 1st character = 2 * frequency of 2nd character.
Example:
Input: str[] = “aaaabbc”
Output: Yes
Explanation: The substring str[0… 5] = “aaaabb” of the given string is composed of only two characters ‘a’ and ‘b’ and frequency of ‘a’ = 2 * frequency of ‘b’, i.e, 4 = 2 * 2. Another example of a valid substring is str[4… 6] = “bbc”.Input: str[] = “abcdefg”
Output: No
Naive Approach: The given problem can be solved by iterating over all the substrings of the given string and checking whether the string is made up of only two characters and the frequency of the 1st character = 2 * frequency of the 2nd character.
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized using a Greedy Technique. Upon observing carefully, it can be noticed that for any substring to be valid, there must exist a substring of size 3 of that string such that it is made up of only two characters and the frequency of the 1st character = 2 * frequency of the 2nd character. Hence, the given problem can be solved by iterating through the given string and for each substring of length 3, check if there exists a string of the form “xxy“, “xyx“, or “yxx“.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if there exist a // substring such that it is made up of // only two characters and freq of 1st // char is equal to 2 * freq of 2nd char bool isPossible(string str) { // Loop to iterate over the string for ( int i = 0; i + 2 < str.size(); i++) { // If the string is of // the form "xxy" if (str[i] == str[i + 1] && str[i] != str[i + 2]) { return true ; } // If the string is of // the form "xyx" if (str[i] == str[i + 2] && str[i] != str[i + 1]) { return true ; } // If the string is of // the form "yxx" if (str[i + 1] == str[i + 2] && str[i] != str[i + 1]) { return true ; } } // If no valid substring exist return false ; } // Driver Code int main() { string str = "aaaabbc" ; if (isPossible(str)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java program for the above approach import java.io.*; public class GFG { // Function to check if there exist a // substring such that it is made up of // only two characters and freq of 1st // char is equal to 2 * freq of 2nd char public static boolean isPossible(String str) { // Loop to iterate over the string for ( int i = 0 ; i + 2 < str.length(); i++) { // If the string is of // the form "xxy" if (str.charAt(i) == str.charAt(i + 1 ) && str.charAt(i) != str.charAt(i + 2 )) { return true ; } // If the string is of // the form "xyx" if (str.charAt(i) == str.charAt(i + 2 ) && str.charAt(i) != str.charAt(i + 1 )) { return true ; } // If the string is of // the form "yxx" if (str.charAt(i + 1 ) == str.charAt(i + 2 ) && str.charAt(i) != str.charAt(i + 1 )) { return true ; } } // If no valid substring exist return false ; } // Driver Code public static void main(String args[]) { String str = "aaaabbc" ; if (isPossible(str)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by saurabh_jaiswal. |
Python3
# Python3 program for the above approach # Function to check if there exist a # substring such that it is made up of # only two characters and freq of 1st # char is equal to 2 * freq of 2nd char def isPossible( str ): # Loop to iterate over the string for i in range ( 0 , len ( str ) - 2 ): # If the string is of # the form "xxy" if ( str [i] = = str [i + 1 ] and str [i] ! = str [i + 2 ]): return True # If the string is of # the form "xyx" if ( str [i] = = str [i + 2 ] and str [i] ! = str [i + 1 ]): return True # If the string is of # the form "yxx" if ( str [i + 1 ] = = str [i + 2 ] and str [i] ! = str [i + 1 ]): return True # If no valid substring exist return False # Driver Code if __name__ = = "__main__" : str = "aaaabbc" if (isPossible( str )): print ( "Yes" ) else : print ( "No" ) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; class GFG { // Function to check if there exist a // substring such that it is made up of // only two characters and freq of 1st // char is equal to 2 * freq of 2nd char public static bool isPossible(String str) { // Loop to iterate over the string for ( int i = 0; i + 2 < str.Length; i++) { // If the string is of // the form "xxy" if (str[i] == str[i + 1] && str[i] != str[i + 2]) { return true ; } // If the string is of // the form "xyx" if (str[i] == str[i + 2] && str[i] != str[i + 1]) { return true ; } // If the string is of // the form "yxx" if (str[i + 1] == str[i + 2] && str[i] != str[i + 1]) { return true ; } } // If no valid substring exist return false ; } // Driver Code public static void Main() { String str = "aaaabbc" ; if (isPossible(str)) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by saurabh_jaiswal. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to check if there exist a // substring such that it is made up of // only two characters and freq of 1st // char is equal to 2 * freq of 2nd char function isPossible( str) { // Loop to iterate over the string for (let i = 0; i + 2 < str.length; i++) { // If the string is of // the form "xxy" if (str[i] == str[i + 1] && str[i] != str[i + 2]) { return true ; } // If the string is of // the form "xyx" if (str[i] == str[i + 2] && str[i] != str[i + 1]) { return true ; } // If the string is of // the form "yxx" if (str[i + 1] == str[i + 2] && str[i] != str[i + 1]) { return true ; } } // If no valid substring exist return false ; } // Driver Code let str = "aaaabbc" ; if (isPossible(str)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by Potta Lokesh </script> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!