Partición máxima de strings

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ón  no 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++ 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 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 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# 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

<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>

11

Complejidad de tiempo: O(N), donde N es la longitud de la string.