Checks whether a string can be split into three substrings, where one substring is a substring of the other two substrings

In this problem, we need to split the given string so that the third substring can be a substring of the first two substrings.

Let's think of a solution. The third string can be a substring of the first two strings only if the first two strings contain all the characters of the third string. So, we need to find at least one character with frequency greater than 3 in the given string, and we can take the third substring of that single character.

Problem Statement - We are given a string str containing N lowercase alphabetic characters. We need to check if we can split the string into three substrings a, b and c such that substring c is a substring of a and b. Print "yes" or "no" depending on whether 3 substrings can be found.

Example

Input –  str = "tutorialsPoint"

Output – ‘Yes’

illustrate

Here, we can split the string into "tu", "torialsPoin" and "t". Therefore, the third string is a substring of the first two strings.

Input –  str = "tutorials"

Output – ‘No’

illustrate

We cannot split the string into three substrings based on the given condition because the frequency of any character is not greater than 3.

Input –  str = "hhhhhhhh"

Output – ‘Yes’

illustrate

According to the given conditions, the three substrings can be 'h', 'h' and 'hhhhhh'.

method 1

In this method, we will use an array to store the frequency of each character. After that, we will check for characters with frequency greater than or equal to 3.

algorithm

• Step 1 - Define the "freq" array with length equal to 26.

• Step 2 - Loop through the string to count the frequency of characters. In the for loop, increment the value of freq[str[i] – ‘a’]. Here, str[i] – ‘a’ gives an index between 0 and 26.

• Step 3 - Now, loop through the "freq" array and return true if the value at any array index is greater than "3".

• Step 4 - Return true when the loop terminates.

• Step 5 - Print "Yes" or "No" based on the return value of the isSUbStringPossible() function.

Example

#include <bits/stdc++.h>
using namespace std;
// function to Check if a string can be split into 3 substrings such that one of them is a substring of the other two
string isSubStringPossible(string str, int len){

   // array to store the frequency
   int freq[26] = {0};
   
   // Iterate over the string
   for (int i = 0; i < len; i++){
   
      // count the frequency of each character
      freq[str[i] - 'a']++;
   }
   
   // Traverse the frequency array
   for (int i = 0; i < 26; i++){
   
      // If the frequency of any character is greater than or equal to 3, then return "Yes."
      if (freq[i] >= 3){
         return "Yes";
      }
   }
   
   // Otherwise
   return "No";
}
int main(){
   string str = "tutorialsPoint";
   int len = str.length();
   cout << "The given string can be splited into 3 substrings such that one of them is a substring of the other two - " << isSubStringPossible(str, len);
   return 0;
}

Output

The given string can be splited into 3 substrings such that one of them is a substring of the other two - Yes

Time complexity - O(N), when we iterate over the string.

Space complexity - O(1) since we use constant length arrays.

Method 2

In this method, we first convert the string into a character array. After that, we use the count() method to count the frequency of specific characters in the array.

algorithm

• Step 1 - Create an array of size "len 1", where "len" is the string length.

• Step 2 - Use the strcpy() method to copy the string into a char array.

• Step 3 - Use a for loop for a total of 26 iterations.

• Step 4 - In a for loop, use the count() method to count the number of occurrences of a specific character.

The

count() method takes a reference to the starting position as the first argument, a reference to the ending position as the second argument, and a character as the third argument.

Here, we need to pass the ASCII value of the character as a parameter and we use I ‘a’ to get the value.

• Step 5 - Returns true if the count() method returns greater than or equal to 3.

• Step 6 - Return false when the loop terminates.

Example

#include <bits/stdc++.h>
using namespace std;
// function to Check if a string can be split into 3 substrings such that one of them is a substring of the other two
string isSubStringPossible(string str, int len){

   //    converting str to char array.
   char char_array[len + 1];
   
   // copy string to char array
   strcpy(char_array, str.c_str());
   
   // make 26 iterations
   for (int i = 0; i < 26; i++){
   
      // Using count() to count the occurrence of each character in the array, and return 'yes' if any character occurs more than 2 times.
      if (count(char_array, char_array + len, i + 'a') >= 2)
         return "YES";
   }
   return "NO";
}
int main(){
   string str = "tutorials";
   int len = str.length();
   cout << "The given string can be splited into 3 substrings such that one of them is a substring of the other two - " << isSubStringPossible(str, len);
   return 0;
}

Output

The given string can be splited into 3 substrings such that one of them is a substring of the other two - Yes

Time complexity - O(N) because count() method iterates over char array to count the number of characters. Also, the strcpy() method takes O(N) time.

Space complexity - O(N) since we store the string into a character array.

in conclusion

We learned two ways to split a string into three substrings, so that one substring can become a substring of two other substrings. The code of the second method is more readable and friendly to beginners, but it is more expensive in time and space.

The above is the detailed content of Checks whether a string can be split into three substrings, where one substring is a substring of the other two substrings. For more information, please follow other related articles on the PHP Chinese website!