Split Four Distinct Strings

Problem Statement

In the “Split Four Distinct Strings” problem we have to check if the given input string can split into 4 strings such that each string is non-empty and different from each others.

Input Format

The first and only one lone containing string “s”.

Output Format

Print “Yes” if we divide the given string into four unequal substrings else print “No”.

Constraints

• 1<=|s|<=10^6
• s[i] must be a lower case alphabet

Example

tutorialscup

Yes

Explanation: Here, we know the length of the string is more than 10 then we can easily break string into substring of length 1, 2, 3 and n-6 where n is the length of the given string “s”.

aabab

No

Algorithm to Split Four Distinct Strings

1. If the length of the string is greater than or equal to 10, return true. Here, if the length is equal to 10, strings with lengths 1, 2, 3, 4 can be formed which are distinct. So, return true.

2. Else run brute force technique to finding four sub-strings that are different and can form the given input string.

Implementation

C++ Program to Split Four Distinct Strings

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    string str;
    cin>>str;
    int flag=0;
    if (str.length() >= 10)
    {
        flag=1;
    }
    for (int i = 1; i < str.size(); i++)
    {
        for (int j = i + 1; j < str.size(); j++)
        {
            for (int k = j + 1; k < str.size(); k++)
            {
                string sub1 = str.substr(0, i);
                string sub2 = str.substr(i, j - i);
                string sub3 = str.substr(j, k - j);
                string sub4 = str.substr(k, str.size() - k);
                if(sub1 != sub2 && sub1 != sub3 && sub1 != sub4 && sub2 != sub3 && sub2 != sub4 && sub3 != sub4)
                {
                    flag=1;
                    goto label;
                }
            }
        }
    } 
    label:;
    if(flag)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    return 0;
}

Java Program to Split Four Distinct Strings

import java.util.Scanner;

class sum
{ 
  public static boolean strcheck(String s1, String s2) 
  { 
    if(s1.compareTo(s2) != 0)
                {
                    return true;
                }
                return false;
  } 
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                int flag=0;
    if(s.length()>=10)
                {
                    flag=1;
                }
    else
                { 
                    for (int i = 1; i < s.length(); i++) 
                    { 
                            for (int j = i + 1; j < s.length(); j++) 
                            { 
                                    for (int k = j + 1; k < s.length(); k++) 
                                    { 
                                            String s1 = "", s2 = "", s3 = "", s4 = ""; 
                                            s1 = s.substring(0, i); 
                                            s2 = s.substring(i, j); 
                                            s3 = s.substring(j, k); 
                                            s4 = s.substring(k, s.length());
                                            if(strcheck(s1, s2) && strcheck(s1, s3) && strcheck(s1, s4) && strcheck(s2, s3) && strcheck(s2, s4) && strcheck(s3, s4)) 
                                            {
                                                    flag=1; 
                                            }
                                    } 
                            } 
                    } 
                }
                if(flag==1)
                {
                    System.out.println("Yes");
                }
                else
                {
                    System.out.println("No");
                }
  } 
} 

abcd

Yes

Complexity Analysis to Split Four Distinct Strings

Time Complexity

If the length of the string is greater than or equal to 10 then the time complexity is O(1). And otherwise, the time complexity will be O(n^4) where n is the size of the string “s”.

Space Complexity

O(1) because we don’t use any auxiliary space here. Here we simply calculate the answer without storing any data.