Dada una string. La tarea es encontrar el número máximo P , de modo que una string determinada pueda dividirse en P substrings contiguas de modo que dos substrings adyacentes sean diferentes. Más formalmente, y
.
Ejemplos:
Entrada: str = “aabccd”
Salida: 4
Explicación:
Podemos dividir la string dada en cuatro strings, como “a”, “ab”, “c”, “cd”. No podemos dividirlo
son más de cuatro partes. Si lo hacemos, entonces la condiciónno se cumplirá
.Entrada: str = “aaaa”
Salida: 3
Acercarse:
- Aquí solo tenemos que centrarnos en el valor de P, no en encontrar esas P substrings.
- Lo resolveremos con avidez. Siempre comparamos la string actual que tenemos con la string anterior que ya se ha tomado.
- Si encontramos que ambos son iguales, continuaremos; de lo contrario, crearemos una partición aquí y cambiaremos la pista anterior de la string a la string actual, lo que significa que trataremos esta string actual como la string anterior para comparación futura.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Return the count of string int maxPartition(string s) { // P will store the answer int n = s.length(), P = 0; // Current will store current string // Previous will store the previous // string that has been taken already string current = "", previous = ""; for (int i = 0; i < n; i++) { // Add a character to current string current += s[i]; if (current != previous) { // Here we will create a partition and // update the previous string with // current string previous = current; // Now we will clear the current string current.clear(); // Increment the count of partition. P++; } } return P; } // Driver code int main() { string s = "geeksforgeeks"; int ans = maxPartition(s); cout << ans << "\n"; return 0; }
Java
// Java implementation of the above approach class GFG { // Return the count of string static int maxPartition(String s) { // P will store the answer int n = s.length(), P = 0; // Current will store current string // Previous will store the previous // string that has been taken already String current = "", previous = ""; for (int i = 0; i < n; i++) { // Add a character to current string current += s.charAt(i); if (!current.equals(previous)) { // Here we will create a partition and // update the previous string with // current string previous = current; // Now we will clear the current string current = ""; // Increment the count of partition. P++; } } return P; } // Driver code public static void main (String[] args) { String s = "geeksforgeeks"; int ans = maxPartition(s); System.out.println(ans); } } // This code is contributed by ihritik
Python3
# Python3 implementation of the above approach # Return the count of string def maxPartition(s): # P will store the answer n = len(s) P = 0 # Current will store current string # Previous will store the previous # that has been taken already current = "" previous = "" for i in range(n): # Add a character to current string current += s[i] if (current != previous): # Here we will create a partition and # update the previous with # current string previous = current # Now we will clear the current string current = "" # Increment the count of partition. P += 1 return P # Driver code s = "geeksforgeeks" ans = maxPartition(s) print(ans) # This code is contributed by Mohit Kumar
C#
// C# implementation of the above approach using System; class GFG { // Return the count of string static int maxPartition(string s) { // P will store the answer int n = s.Length, P = 0; // Current will store current string // Previous will store the previous // string that has been taken already string current = "", previous = ""; for (int i = 0; i < n; i++) { // Add a character to current string current += s[i]; if (!current.Equals(previous)) { // Here we will create a partition and // update the previous string with // current string previous = current; // Now we will clear the current string current = ""; // Increment the count of partition. P++; } } return P; } // Driver code public static void Main () { string s = "geeksforgeeks"; int ans = maxPartition(s); Console.WriteLine(ans); } } // This code is contributed by ihritik
Javascript
<script> // Javascript implementation of the above approach // Return the count of string function maxPartition(s) { // P will store the answer var n = s.length, P = 0; // Current will store current string // Previous will store the previous // string that has been taken already var current = "", previous = ""; for (var i = 0; i < n; i++) { // Add a character to current string current += s[i]; if (current != previous) { // Here we will create a partition and // update the previous string with // current string previous = current; // Now we will clear the current string current = ""; // Increment the count of partition. P++; } } return P; } // Driver code var s = "geeksforgeeks"; var ans = maxPartition(s); document.write( ans); </script>
Producción:
11
Complejidad de tiempo: O(N), donde N es la longitud de la string.