Split the String

Easy
0/40
profile
Contributed by
13 upvotes
Asked in companies
Morgan StanleyLinkedInAmazon

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

2
8
abcababc
6
aaaaaa

Sample Output 1:

true
true

Explanation of Sample Input 1:

Test Case 1:
Given ‘str' = ”abcababc”
Possible split can be “abc”, “ab”, “abc”
So we can see that “ab” is a substring of both “abc”

Test Case 2:
Given ‘str’ = “aaaaaa”
Possible split can be “aa”,  “aa”,  “aa”
All 3 strings are equal. We can say that “aa” is a substring of both “aa”.

Sample Input 2:

2
5
abcde
2
aa

Sample Output 2:

false
false

Explanation of Sample Input 2:

Test Case 1 :  
Given ‘str’ = “abcde”
There is no possible way to split ‘str’ into 3 non-empty substrings so the answer is false


Test Case 2 : 
Given ‘str’ = “aa”
There is no possible way to split ‘str’ into 3 non-empty substrings so the answer is false
Hint

Can you check all possible splitting of a string into 3 substrings?

Approaches (2)
Brute-force

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.
  • 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.
Time Complexity

O(N ^ 3), where ‘N’ is the total number of characters in the given string.

 

In the worst case, we need to check all possible splitting. It will take O(N ^ 2) time and our checking substring function takes O(N) time as we are traversing a string. Hence the overall time complexity is O(N ^ 3). 

Space Complexity

O(N), where N is the total number of characters in the string. 

 

Storing the 3 split substrings will take O(N) space complexity.

Code Solution
(100% EXP penalty)
Split the String
Full screen
Console