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;

}

Accepted Answer

THis is my answers. Jhwoef hoh fewiudcb ifvbd iubd wisajbufj

Accepted Answer

For each case print true the given string can be split or else print false without quoter

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 Infosys Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in Infosys Software Engineer