Check if a string contains two non overlapping sub-strings “geek” and “keeg”

0 0 3 minutes read

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>

Output

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.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!