Split the String
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

Question

Split the String

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.

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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

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

Time Complexity: O(n^3)Explanation:

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).

Java (SE 1.8)


/* 
	Time complexity: O(N ^ 3)
	Space complexity: O(N)

	Where N is the length of the string 
*/
import java.util.Arrays;

public class Solution {

	// Function for checking 'a' is substring of 'b' or not
	public static boolean isSubstring(String a, String b) {
	
		// We will be using inbuilt function of java indexOf()
		// The indexOf function takes a string as a parameter and give us first
		// occurrence
		// of string
		int index = b.indexOf(a);
		if (index != -1) {
		
			// Index is not pointing -1 means we got 'a' as a substring of
			// string 'b'
			return true;
		}

		// Otherwise we did not get any occurrence of the string 'a' in string 'b'
		return false;
	}

	public static boolean splitString(String s) {
		int n = s.length();
		for (int i = 1; i <= (n - 2); i++) {
			for (int j = i; j <= (n - 2); j++) {

				// String a is from 0 to i-1
				String a = s.substring(0, i);

				// String b will start from i to j
				String b = s.substring(i, j + 1);

				// String c from j+1 to n-1
				String c = s.substring(j + 1);
				
				// check if any string from a, b, c is a substring of another two.
				if ((isSubstring(a, b) && isSubstring(a, c)) || (isSubstring(b, a) && isSubstring(b, c))
						|| (isSubstring(c, b) && isSubstring(c, a))) {
					return true;
				}
			}
		}
		return false;
	}
}

Python (3.5)

'''

   Time complexity: O(N ^ 3)

   Space complexity: O(N)



   Where N is the length of the string 



'''



# Function to check for substring.

def isSubstring(a, b):



	if(b.find(a) == -1):

		return False

	

	return True



def splitString(s):

	

	n = len(s)

	

	for i in range(1, n - 1):

		for j in range(i, n -1):

			

			# String 'a' is from 0 to i-1

			a = s[0:i]

			

			# String 'b' will start from i to j

			b = s[i:j+1]

			

			# String 'c' from j+1 to n-1

			c = s[j+1: n]

			

			# Check if any string from a, b, c is a substring of another two.

			if ((isSubstring(a, b) and isSubstring(a, c)) or (isSubstring(b, a) and isSubstring(b, c))  or (isSubstring(c, b) and isSubstring(c, a))):

				return True

				

	return False

C++ (g++ 5.4)

/* 

   Time complexity: O(N ^ 3)

   Space complexity: O(N)



   Where N is the length of the string 

*/



// Function for checking 'a' is substring of 'b' or not

bool isSubstring(string &a, string &b)

{

    // We will be using inbuilt function of c++ s.find()



    // The find function takes a string as a parameter and give us first occurance of string

    size_t index = b.find(a);



    if (index != string::npos)

    {

        // Index is not pointing endpoint of string means we got 'a' as a substring of string 'b'

        return true;

    }

    

    // Otherwise we did not get any occurrence of the string 'a' in string 'b'

    return false;

}



bool splitString(string &s)

{

    int n = s.size();

    for (int i = 1; i <= (n - 2); i++)

    {

        for (int j = i; j <= (n - 2); j++)

        {

        	

            // String a is from 0 to i-1

            string a = s.substr(0, i);

            

            //  String b will start from i to j

            string b = s.substr(i, j - i + 1);



            //  String c from j+1 to n-1

            string c = s.substr(j + 1);



             // check if any string from a, b, c is a substring of another two.

			if ((isSubstring(a, b) && isSubstring(a, c)) || (isSubstring(b, a) && isSubstring(b, c))  || (isSubstring(c, b) && isSubstring(c, a))) 

			{

			     return true;

			}

        }

    }

    return false;

}

Accepted Answer

Greedy

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.

Space Complexity: O(1)Explanation:

O(26).

For storing frequency of 26 lowercase alphabets.

Time Complexity: O(n)Explanation:

O(1),

When ‘N’ > 52, then time complexity is O(1), it’s faster in the case of larger values of N. When ‘N’ ≤ 52, then we are traversing a string of length ‘N’ and an array of length 26 that takes at most 52 operations, hence the overall time complexity will be O(1).

Python (3.5)

'''

   Time complexity : O(1)

   Space complexity : O(26)



'''



def splitString(s):

	

	n = len(s)

	

	# Check size of string if it is greater than 52 then return True

	if (n > 52):

		return True

		

	# Storing frequency of each character in string.

	freq = [0 for i in range(26)]

	

	# Traverse the string

	for i in s:



		# Increment frequency of current character

		freq[ord(i) - ord('a')] += 1

		

	# Traverse the freq arr

	for i in range(26):



		# If any character occurs  3 or more times return True

		if (freq[i] >= 3):

			return True



	# There is no character with frequency 3 or more hence there is no possible spiltting.

	return False

Java (SE 1.8)


/* 
	Time complexity : O(N)  for n<=52 and O(1) for N>52
	Space complexity : O(26)

	Where N is length of string 
*/
import java.util.Arrays;

public class Solution {

	public static boolean splitString(String s) {
		int n = s.length();
		
		// Check size of string if it is greater than 52 return true
		if (n > 52) {
			return true;
		}

		// Storing frequency of each characters in string
		int freq[] = new int[26];
		Arrays.fill(freq, 0);

		// Traverse string
		for (int i = 0; i < n; i++) {
		
			// Increment frequency of current character
			freq[s.charAt(i) - 'a']++;
		}

		// Traverse freq arr
		for (int i = 0; i < 26; i++) {
		
			// If any character occurs 3 or more times return true
			if (freq[i] >= 3) {
				return true;
			}
		}

		// There is no character with frequency 3 or more hence there is no possible spiltting return false;
		return false;
	}

}

C++ (g++ 5.4)

/* 

   Time complexity : O(1) 

   Space complexity : O(26)



*/



bool splitString(string &s)

{

    int n = s.size();



    // Check size of string if it is greater than 52 then return true

    if (n > 52)

    {

        return true;

    }



    // Storing frequency of each characters in string

    vector freq(26, 0);



    // Traverse the string

    for (int i = 0; i < n; i++)

    {

        // Increment frequency of current character

        freq[s[i] - 'a']++;

    }



    // Traverse the freq arr

    for (int i = 0; i < 26; i++)

    {

        // If any characters occurs  3 or more times return true

        if (freq[i] >= 3)

        {

            return true;

        }

    }



    // There is no character with frequency 3 or more hence there is no possible spiltting then return false.

    return false;

}

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:

Note:

Input Format:

Output Format:

Constraints:

Note:

Top Nutanix Mts1 interview questions & answers

Popular interview questions of Mts1