Dada uma string, a tarefa é verificar se podemos dividi-la em 4 strings de forma que cada string não seja vazia e seja diferente da outra.
Exemplos:
Entrada : str[] = 'geeksforgeeks'
Saída : Sim
'geeks' 'for' 'gee' 'ks' são quatro strings distintas que podem ser formadas a partir de uma determinada string.
Entrada : str[] = 'aaabb'
Saída : Não
Observe se o comprimento da string é maior ou igual a 10 então cada vez pode ser dividida em quatro partes. Suponha que o comprimento seja 10, então uma corda de comprimento 1 2 3 4 pode ser feita.
Para strings com comprimento inferior a 10, podemos usar força bruta, ou seja, iterar todas as formas possíveis de dividir a string e verificar cada uma delas.
Se comprimento é superior a 10
retornar verdadeiro
Outro (Se o comprimento for inferior a 10)
Use o método Brute Force para verificar se podemos quebrá-lo em quatro strings distintas.
Abaixo está a implementação da ideia acima.
C++// C++ program to check if we can break a string // into four distinct strings. #include
// Java program to check if we can break a string // into four distinct strings. class GFG { // Return true if both strings are equal public static boolean strcheck(String s1 String s2) { if (s1 != s2) return false; return true; } // Return if the given string can be split or not. public static boolean check(String s) { if (s.length() >= 10) return true; // Brute Force 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++) { // Making 4 string from the given string String s1 = '' s2 = '' s3 = '' s4 = ''; try { s1 = s.substring(0 i); s2 = s.substring(i j - i); s3 = s.substring(j k - j); s4 = s.substring(k s.length() - k); } catch (StringIndexOutOfBoundsException e) { } // Checking if they are distinct or not. if (strcheck(s1 s2) && strcheck(s1 s3) && strcheck(s1 s4) && strcheck(s2 s3) && strcheck(s2 s4) && strcheck(s3 s4)) return true; } } } return false; } // Driver code public static void main(String[] args) { String str = 'aaabb'; if (check(str)) System.out.println('Yes'); else System.out.println('No'); } } // This code is contributed by // sanjeev2552
# Python3 program to check if we can # break a into four distinct strings. # Return if the given string can be # split or not. def check(s): # We can always break a of size 10 or # more into four distinct strings. if (len(s) >= 10): return True # Brute Force for i in range(1 len(s)): for j in range(i + 1 len(s)): for k in range(j + 1 len(s)): # Making 4 from the given s1 = s[0:i] s2 = s[i:j - i] s3 = s[j: k - j] s4 = s[k: len(s) - k] # Checking if they are distinct or not. if (s1 != s2 and s1 != s3 and s1 != s4 and s2 != s3 and s2 != s4 and s3 != s4): return True return False # Driver Code if __name__ == '__main__': str = 'aaabb' print('Yes') if(check(str)) else print('NO') # This code is contributed # by SHUBHAMSINGH10
// C# program to check if we can break a string // into four distinct strings. using System; class GFG { // Return true if both strings are equal public static Boolean strcheck(String s1 String s2) { if (s1.CompareTo(s2) != 0) return false; return true; } // Return if the given string // can be split or not. public static Boolean check(String s) { if (s.Length >= 10) return true; // Brute Force 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++) { // Making 4 string from the given string String s1 = '' s2 = '' s3 = '' s4 = ''; try { s1 = s.Substring(0 i); s2 = s.Substring(i j - i); s3 = s.Substring(j k - j); s4 = s.Substring(k s.Length - k); } catch (Exception e) { } // Checking if they are distinct or not. if (strcheck(s1 s2) && strcheck(s1 s3) && strcheck(s1 s4) && strcheck(s2 s3) && strcheck(s2 s4) && strcheck(s3 s4)) return true; } } } return false; } // Driver code public static void Main(String[] args) { String str = 'aaabb'; if (check(str)) Console.WriteLine('Yes'); else Console.WriteLine('No'); } } // This code is contributed by Princi Singh
<script> // JavaScript program to check if we can break a string // into four distinct strings. // Return true if both strings are equal function strcheck(s1 s2) { if (s1.localeCompare(s2) != 0) return false; return true; } // Return if the given string can be split or not. function check(s) { if (s.length >= 10) return true; // Brute Force for (let i = 1; i < s.length; i++) { for (let j = i + 1; j < s.length; j++) { for (let k = j + 1; k < s.length; k++) { // Making 4 string from the given string let s1 = '' s2 = '' s3 = '' s4 = ''; s1 = s.substring(0 i); s2 = s.substring(i i + j - i); s3 = s.substring(j j + k - j); s4 = s.substring(k k + s.length - k); // Checking if they are distinct or not. if (strcheck(s1 s2) && strcheck(s1 s3) && strcheck(s1 s4) && strcheck(s2 s3) && strcheck(s2 s4) && strcheck(s3 s4)) return true; } } } return false; } let str = 'aaabb'; if (check(str)) document.write('Yes'); else document.write('No'); </script>
// Return true if the given string can be split into four distinct strings function check($s) { // We can always break a string of size 10 or more into four distinct strings if (strlen($s) >= 10) { return true; } // Brute Force for ($i = 1; $i < strlen($s); $i++) { for ($j = $i + 1; $j < strlen($s); $j++) { for ($k = $j + 1; $k < strlen($s); $k++) { // Making 4 from the given string $s1 = substr($s 0 $i); $s2 = substr($s $i $j - $i); $s3 = substr($s $j $k - $j); $s4 = substr($s $k strlen($s) - $k); // Checking if they are distinct or not if ($s1 != $s2 && $s1 != $s3 && $s1 != $s4 && $s2 != $s3 && $s2 != $s4 && $s3 != $s4) { return true; } } } } return false; } // Driver Code $str = 'aaabb'; echo (check($str) ? 'Yes' : 'NO'); ?> Saída
No
Complexidade de tempo : Sobre3)
Espaço Auxiliar: Sobre)
Criar questionário