Given a string S, you have to check if we can split it into four strings such that each string is non-empty and distinct from each other.
 
Example 1:
Input :
S = "geeksforgeeks"
Output:
1
Explanation:
"geeks", "for", "gee", "ks" are four
distinct strings that can form from
given string.
Example 2:
Input: 
S = "aaabb" 
Output:
0
Explanation:
It's not possible to split string S in four
distinct strings
Your Task:  
You don't need to read input or print anything. Your task is to complete the function isPossible() which takes the string S as input parameter and returns 1 if it's possible to split S into four strings such that each string is non-empty and distinct from each other or return 0 otherwise. 
 
Expected Time Complexity: O(|S|^{3})
Expected Space Complexity: O(1)
Constraints:
1< |S| <=10000

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def isPossible (self, S):
        # code here 

Solutions:
class Solution:

	def isPossible(self, S):
		n = len(S)
		if n <= 3:
			return 0
		if n >= 10:
			return 1
		if n > 3 and n < 10:
			st = set()
			for ch in S:
				st.add(ch)
			size = len(st)
			if size > 3:
				return 1
			elif size == 3 and n >= 5:
				return 1
			elif size == 2 and n >= 7:
				return 1
			else:
				return 0


class Solution:

	def isPossible(self, S):
		n = len(S)
		for i in range(1, n):
			s1 = S[:i]
			for j in range(i + 1, n):
				s2 = S[i:j]
				for k in range(j + 1, n):
					s3 = S[j:k]
					s4 = S[k:n]
					if s1 != s2 and s1 != s3 and (s1 != s4) and (s2 != s3) and (s2 != s4) and (s3 != s4):
						return 1
		return 0


class Solution:

	def isPossible(self, S):
		s = set()
		i = 1
		while i <= len(S):
			if S[:i] not in s:
				s.add(S[:i])
				S = S[i:]
				i = 1
			else:
				i += 1
		return int(len(s) > 3)


class Solution:

	def isPossible(self, s):
		if len(s) >= 10:
			return 1
		a = []
		for i in s:
			if i not in a:
				a.append(i)
		if len(a) >= 4:
			return 1
		for i in range(1, len(s)):
			for j in range(i + 1, len(s)):
				for k in range(j + 1, len(s)):
					s1 = s[0:i]
					s2 = s[i:j - i + 1]
					s3 = s[j:k - j + 1]
					s4 = s[k:len(s) - k + 1]
					if s1 != s2 and s1 != s3 and (s1 != s4) and (s2 != s3) and (s2 != s4) and (s3 != s4):
						return 1
		return 0


class Solution:

	def isPossible(self, S):
		n = len(S)
		for i in range(0, n - 3):
			first = S[0:i + 1]
			for j in range(i + 1, n - 2):
				second = S[i + 1:j + 1]
				if first == second:
					continue
				else:
					for k in range(j + 1, n - 1):
						third = S[j + 1:k + 1]
						if third in [first, second]:
							continue
						else:
							fourth = S[k + 1:]
							if fourth in [first, second, third]:
								continue
							else:
								return 1
		return 0