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 codeint main(){ char s[] = "geekeekeeg"; if (isValid(s)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachclass 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 codepublic 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 codeif __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 Codevar 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.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
