Check if a Substring Exists, having Only Two Distinct Characters with The Frequency of One as Twice The Others

Naive Approach

One possible solution for this problem involves iterating over all possible substrings of the given string and verifying if they meet certain conditions. However, since there are N^2 possible substrings to consider and checking each one takes O(N) time, the time complexity of this approach is O(N^3), which is not very efficient.

We will now look at the naive approach first and then move on to the optimized approach.

Algorithm

1. Set the length of the input string ‘s’ to ‘n’.
    
2. Loop through all possible substrings of ‘s’ by iterating over all pairs of indices ‘i’ and ‘j’ such that 0 ≤ i < j < n.
    
3. For each substring, initialize an array ‘freq’ of size 26 with all elements set to 0 to count the frequency of characters between i and j.
    
4. Loop through the characters of the substring between i and j and increment the corresponding element of the freq array for each character encountered.
    
5. Initialize a counter called 'distinct’ for counting the number of distinct characters in the substring by looping through the freq array and incrementing the variable distinct for each element with a value greater than 0.
    
6. If distinct is equal to 2, find the frequency count of the two distinct characters by looping through the freq array and setting the variables ‘cnt1’ and ‘cnt2’ to their respective frequency counts. If either ‘cnt1’ is twice of ‘cnt2’ or ‘cnt2’ is twice of ‘cnt1’, return true.
    
7. If no substring satisfies the condition in step 6 is found, return false.

Dry Run

Let’s dry run the code for string, s[]= ‘abb’.

• Set ‘n’ to 3 (the length of s).
   
• Iterate through all possible substrings of ‘s’.
   
• Here, the substring is "ab" and the freq array becomes  {1, 1, 0, ..., 0}. Here, the frequency of ‘a’ is one because ‘a’ appears once. Similarly, the frequency of ‘b’ is one because ‘b’ appears once. Therefore distinct = 2, cnt1 = 1, cnt2 = 1.
  The condition ((cnt1 == 2cnt2) || (cnt2 == 2cnt1)) is not satisfied.

• Now we increment the j pointer. Here, the substring is "abb" and the freq array: {1, 2, 0, ..., 0}. 
  As ‘a’ appears once, hence it will store 1 in freq. And ‘b’ appears twice. Hence it will further store 2 in the freq array. 
  Therefore, distinct = 2, cnt1 = 1, cnt2 = 2. 
  Here the condition ((cnt1 == 2cnt2) || (cnt2 == 2cnt1)) is satisfied, return ‘true’.

• Since a substring satisfying the condition is found, the function returns true.

Code in C++

#include <iostream>
#include <string>
using namespace std;

bool checkSubstring(string s) {
    int n = s.length();
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            /* 
                Counting the frequency of characters between i and j
                using an integer array freq of size 26. 
            */
            int freq[26] = {0};
            for (int k = i; k <= j; k++) {
                /* 
                    Increment the frequency of the
                    character at the kth position of s
                */
                freq[s[k]-'a']++; 
            }
            
            /* 
                Checking if only two distinct characters exist 
                and the first character's frequency is twice the 
                second character or vice versa 
            */
            int distinct = 0, cnt1 = 0, cnt2 = 0;
            for (int k = 0; k < 26; k++) {
                /* 
                    If the frequency of the character
                    at index k is greater than 0
                */
                if (freq[k] > 0) { 
                   /* 
                       Increment the number of distinct
                       characters in the substring
                   */
                   distinct++; 
                   /* 
                       If cnt1 is 0, store the frequency
                       of the current character in cnt1
                   */
                   if (cnt1 == 0) 
                       cnt1 = freq[k]; 
                   /* 
                       if cnt1 is not 0 but cnt2 is 0, store
                       the frequency of the current character in cnt2
                   */
                   else if (cnt2 == 0) 
                       cnt2 = freq[k]; 
                   // if both cnt1 and cnt2 are not 0, break the loop
                   else 
                       break; 
                }
            }
            
            /* 
                If exactly two distinct characters exist
                and the first character's frequency is twice the 
                second character or vice versa, return true 
            */
            if (distinct == 2 && ((cnt1 == 2*cnt2) || (cnt2 == 2*cnt1))) {
                return true;
            }
        }
    }
    // If no such substring exists, return false
    return false; 
}

int main() {
    string s = "abb";
    
    // Calling the function and printing the result 
    if (checkSubstring(s)) {
        cout << "Yes, Substring exists with first character's frequency twice the second character." << endl;
    } 
    else {
        cout << "No, Substring exists with first character's frequency twice the second character." << endl;
    }
    
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Code in Python

def check_substring(s: str) -> bool:
    n = len(s)
    
    for i in range(n):
        for j in range(i + 1, n):
            # Counting the frequency of characters 
            # between i and j using a dictionary
            freq = {}
            
            for k in range(i, j + 1):
                # Increment the frequency of the 
                # character at the kth position of s
                freq[s[k]] = freq.get(s[k], 0) + 1

            # Checking if only two distinct characters
            # exist and the first character's frequency is
            # twice the second character or vice versa
            distinct = len(freq)
            if distinct == 2:
                cnt1, cnt2 = freq.values()
                if cnt1 == 2 * cnt2 or cnt2 == 2 * cnt1:
                    return True

    # If no such substring exists, return false
    return False

if __name__ == '__main__':
    s = 'abb'
    
    # Calling the function and printing the result 
    if check_substring(s):
        print('Yes, Substring exists with first character\'s frequency twice the second character.')
    else:
        print('No, Substring exists with first character\'s frequency twice the second character.')

You can also try this code with Online Python Compiler

Run Code

Output

Complexity

Time Complexity

The time complexity is O(N^3), where ‘N’ represents the length of the input string. This is because the code iterates over all possible substrings of the input string, and for each substring, it counts the frequency of each character, which takes O(N) time.

Space Complexity

The space complexity is O(1) because the amount of memory used by the algorithm remains fixed and does not vary with input size.

Also check out - Substr C++, and Euclid GCD Algorithm

Optimised Approach

By applying a Greedy technique, we can enhance the method mentioned above. Through careful observation, we can deduce that a valid substring must contain a subsequence of three characters with only two distinct characters, where the frequency of the first character is double the frequency of the second character. To solve the problem, we can iterate over all substrings of size three and verify if there is a string in the forms of "yxx", "xyx", or "xxy".

Algorithm

1. Initialize a boolean variable ‘valid’ to false.
    
2. Loop through the characters of the string from index 0 to index str.size() - 2 where str.size() is the length of the input string.
    
3. Inside the loop, check for the following three conditions:
   1. If the current character and the next character are the same and the third character is different, set the valid variable to true and break out of the loop.
      
      For example: In the case of “xxy” the first character and the second character are the same, but the third character is different.
       
   2. If the current character and the third character are the same and the second character is different, set the valid variable to true and break out of the loop.
      
      For example: In the case of “xyx” the first character and the third character are the same, but the second character is different.
       
   3. If the next character and the third character are the same and the current character is different, set the valid variable to true and break out of the loop.
      
      For example: In the case of “yxx” the second character and the third character are the same, but the third character is different.
       
4. Return the value of 'valid'.

Dry Run

• Initialize a boolean variable "valid" to false.
   
• Start a loop from i = 0 to i < str.size() - 2, where str.size() is the length of the input string "abb". Since the length of "abb" is 3, the loop will only run once with i = 0.

• Check the first condition: if (str[i] == str[i + 1] && str[i] != str[i + 2]). Since str[0] = 'a', str[1] = 'b', and str[2] = 'b', this condition evaluates to false because a != b and we skip to the next condition.

• Check the second condition: if (str[i] == str[i + 2] && str[i] != str[i + 1]). Since str[0] = 'a', str[2] = 'b', and str[1] = 'b', this condition evaluates to false because a != b and we skip to the next condition.

• Check the third condition: if (str[i+1] == str[i + 2] && str[i] != str[i + 1]). Since str[0] = 'a', str[2] = 'b', and str[1] = 'b', this condition evaluates to true because b == b and also a != b. So we set the "valid" variable to true and break out of the loop.
   
• Return the value of the "valid" variable, which is true in this case.

Code in C++

#include <bits/stdc++.h>
using namespace std;

bool isPossible(string s) {
    /*
        If string length is less than 3, then 
        no such substring exists 
    */
    if (s.length() < 3) {
        return false;
    }

    bool valid = false;
    for (int i = 0; i < s.size() - 2; i++) {
        /* 
            If there are two consecutive characters 
            in the substring that are same and the 
            next character is different
        */
        if (s[i] == s[i + 1] && s[i] != s[i + 2]) {
            valid = true;
            break;
        }
        
        /* 
            If there are two characters in the substring 
            that are same and the character in between 
            them is different
        */
        if (s[i] == s[i + 2] && s[i] != s[i + 1]) {
            valid = true;
            break;
        }
        
        /* 
            If there are two consecutive characters in the 
            substring that are different and the next 
            character has the same value as the 
            second character
        */
        if (s[i + 1] == s[i + 2] && s[i] != s[i + 1]) {
            valid = true;
            break;
        }
    }
    return valid;
}

// Driver Code
int main() {
    string str = "abb";

    // Calling the function and printing the result
    if (isPossible(str))
        cout << "Yes, Substring exists with first character's frequency twice the second character.";
    else
        cout << "No, Substring does not exist with first character's frequency twice the second character.";

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Code in Python

def is_possible(s):
    if not s:
        return False
        
    valid = False
    for i in range(len(s) - 2):
        
        # If there are two consecutive characters in the 
        # substring that are same and the next character 
        # is different
        if s[i] == s[i + 1] and s[i] != s[i + 2]:
            valid = True
            break
            
        # If there are two characters in 
        # the substring that are same and the
        # character in between them is different
        if s[i] == s[i + 2] and s[i] != s[i + 1]:
            valid = True
            break
    
        # If there are two consecutive characters 
        # in the substring that are different and the 
        # next character has the same value as 
        # the second character
        if s[i + 1] == s[i + 2] and s[i] != s[i + 1]:
            valid = True
            break
    return valid


# Driver Code
str = "abb"

# Calling the function and printing the result 
if is_possible(str):
    print("Yes, Substring exists with first character's frequency twice the second character.")
else:
    print("No, Substring does not exist with first character's frequency twice the second character.")

You can also try this code with Online Python Compiler

Run Code

Output

Complexity

Time Complexity

The time complexity of the given algorithm is O(N), where ‘N’ corresponds to the size of the input string because we iterate through the string to check each character against its adjacent character.

Space Complexity

The space complexity is O(1) because the amount of memory used by the program does not change with the size of the input string.

Check out this problem - Longest Common Prefix

Frequently Asked Questions

What is a substring?

A substring refers to a consecutive set of characters present in a string without any interruptions. It can be of any length, including zero. It can be of any length, including zero.

How to convert a string into an integer using the C++ STL function?

We can use the ‘stoi’ function from C++ STL to convert a string into an integer.

What is the difference between a character and a string?

A character is a single symbol or letter, while a string is a sequence of characters.

How can you compare two strings in c++?

You can use the ‘compare()’ method to compare two strings. We can also use operators ‘==’ and ‘!=’ to compare. We can also use ‘strcmp()’ function when using string.

How can you find the length of a string in C++?

You can use the ‘length()’ method of the string class in C++ to find the length of a string. We can also use the ‘size()’ and ‘strlen()’ function.

Conclusion

In this blog, we learned how to check if a substring exists having only two distinct characters with the frequency of one as twice the other. We have implemented the problem in C++ programming language.

For more string data structure articles, you can refer following links:

• Reverse words in a string 
• Palindromic substrings
• Edit distance
   

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!