Last Updated: 20 May, 2021
Split the String
Easy
Asked in companies
You are given a string ‘str’ of ‘N’ lowercase alphabets. Your task is to check whether it is possible to split the given string into three non-empty substrings such that one of them is a substring of another two.
For example:
‘str’ = 'abcabab', we can split this string into 3 string a, b, c as a = 'abc', b = 'ab', c = 'abc', we can clearly see that b is a substring of both a and c.
Note:
A substring is a contiguous sequence of characters within a string. For example 'ab', 'b' and 'abc' are the substring of string 'abc', but 'ac' is not a substring of 'abc'.
A non-empty substring means a substring with a size greater than 0.
Input Format:
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains a single integer ‘N’ denoting the size of the given string.
The second line of each test case contains a string of size ‘N’.
Output Format:
For each test case, print “true” if the given string can be split, or else print “false” without quotes.
The output of each test case will be printed in a separate line.
Constraints:
1 <= T <= 5
1 <= N <= 10 ^ 5
Where ‘T’ is the number of test cases, ‘N’ is the length of the given string, and the given string contains only lowercase English letters.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Approaches
The idea here is to check all possible ways to divide a string into 3 substrings and check if there is a string that is a substring of the other two parts. We can divide a string into 3 non-empty substrings:
- A non-empty prefix
- A non-empty suffix
- And a non-empty middle string that is between the ending point of the 1st string and starting point of the 2nd string.
Algorithm:
- Run a loop from i = 1 to ‘N’ - 2. Here ‘N’ is the length of the string.
- Run a loop from j = i to ‘N’ - 2.
- Assign 3 stings as a = str[0, i-1], b = str[i, j], c = str[j+1, n-1].
- Call ‘isSubtring’ function to Check for ‘a’ if it is a substring of ‘b’ and ‘c' or ‘b’ is substring of ‘a’ and ‘c’ or ‘c’ is substring of ‘b’ and ‘a’.
- If any of the conditions satisfied then return true.
- Run a loop from j = i to ‘N’ - 2.
- Return false because we did not get any such substring.
Description of ‘isSubstring’ function:
- This function will take 2 parameters string ‘a’ and string ‘b’
- It will return true if ‘a’ is a substring of ‘b’ otherwise it will return false.
bool isSubstring(a, b)
- If ‘a’ is a substring of 'b' then return true.
- Else, return false.
The idea here is to work with a little bit of intuition. We discussed partitioning of string into 3 parts such as prefix+middle part+suffix. Can we fix the length of the middle string to 1 means the middle string will have a single character and a character is always a substring of string if that string contains that character?
Now if a character occurs 3 or more times we can always pick the 2nd occurrence of that character and make that middle string and we can always say that this is a substring of both prefix and suffix strings.
So we just need to check if there is a character that is present 3 or more times in the string.
Additional point: Can we take advantage of the fact that lowercase alphabets are only 26?
Using this fact we can say that when the length of a given string will be >52 we don’t need to check whether a character is occurring 3 or more times or not we can blindly say that there will be at least 1 character that will occur 3 or more times so we will not check string when length will be greater than 52
Algorithm:
- Check size of input string if it is greater than 52 return true otherwise-
- Declare an array of size 26 ‘freq’ with all elements 0.
- Traverse the string ‘str’ and increment the frequency of the current character.
- Run a loop to iterate through the ‘freq’ array.
- If the current element is greater than or equal to 3, then return true.
- Return false.