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
-
Set the length of the input string ‘s’ to ‘n’.
-
Loop through all possible substrings of ‘s’ by iterating over all pairs of indices ‘i’ and ‘j’ such that 0 ≤ i < j < n.
-
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.
-
Loop through the characters of the substring between i and j and increment the corresponding element of the freq array for each character encountered.
-
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.
-
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.
- 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
-
Initialize a boolean variable ‘valid’ to false.
-
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.
-
Inside the loop, check for the following three conditions:
-
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.
-
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.
-
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.
- 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:
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!