Check if a string contains two non overlapping sub-strings “geek” and “keeg”
Given a string str, the task is to check whether the string contains two non-overlapping sub-strings s1 = “geek” and s2 = “keeg” such that s2 starts after s1 ends.
Examples:
Input: str = “geekeekeeg”
Output: Yes
“geek” and “keeg” both are present in the
given string without overlapping.
Input: str = “geekeeg”
Output: No
“geek” and “keeg” both are present but they overlap.
Approach: Check if the sub-string “geek” occurs before “keeg” in the given string. This problem is simpler when we use a predefined function strstr in order to find the occurrence of a sub-string in the given string.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function that returns true // if s contains two non overlapping // sub strings "geek" and "keeg" bool isValid( char s[]) { char * p; // If "geek" and "keeg" are both present // in s without over-lapping and "keeg" // starts after "geek" ends if ((p = strstr (s, "geek" )) && ( strstr (p + 4, "keeg" ))) return true ; return false ; } // Driver code int main() { char s[] = "geekeekeeg" ; if (isValid(s)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java implementation of the approach class GFG { // Function that returns true // if s contains two non overlapping // sub Strings "geek" and "keeg" static boolean isValid(String s) { // If "geek" and "keeg" are both present // in s without over-lapping and "keeg" // starts after "geek" ends if ((s.indexOf( "geek" )!=- 1 ) && (s.indexOf( "keeg" ,s.indexOf( "geek" ) + 4 )!=- 1 )) return true ; return false ; } // Driver code public static void main(String args[]) { String s = "geekeekeeg" ; if (isValid(s)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Arnab Kundu |
Python3
# Python 3 implementation of the approach # Function that returns true # if s contains two non overlapping # sub strings "geek" and "keeg" def isValid(s): p = "" # If "geek" and "keeg" are both present # in s without over-lapping and "keeg" # starts after "geek" ends p = s.find( "geek" ) if (s.find( "keeg" ,p + 4 )): return True return False # Driver code if __name__ = = "__main__" : s = "geekeekeeg" if (isValid(s)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by ChitraNayal |
C#
// C# implementation of the approach using System; class GFG { // Function that returns true // if s contains two non overlapping // sub Strings "geek" and "keeg" static bool isValid( string s) { // If "geek" and "keeg" are both present // in s without over-lapping and "keeg" // starts after "geek" ends if ((s.IndexOf( "geek" )!=-1) && (s.IndexOf( "keeg" ,s.IndexOf( "geek" ) + 4)!=-1)) return true ; return false ; } // Driver code public static void Main() { string s = "geekeekeeg" ; if (isValid(s)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // JavaScript implementation of the approach // Function that returns true // if s contains two non overlapping // sub Strings "geek" and "keeg" function isValid(s) { // If "geek" and "keeg" are both present // in s without over-lapping and "keeg" // starts after "geek" ends if ((s.indexOf( "geek" ) != -1) && (s.indexOf( "keeg" , s.indexOf( "geek" ) + 4) != -1)) return true ; return false ; } // Driver Code var s = "geekeekeeg" ; if (isValid(s)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by Khushboogoyal499 </script> |
Yes
Time Complexity: O(n), for using indexof() function which takes a linear time.
Auxiliary Space: O(n), where n is the length of the given string.
Contact Us