Dividir una string en el número máximo de substrings únicas

Dada la string str , la tarea es dividir la string en el máximo número posible de substrings únicas e imprimir su recuento.

Ejemplos: 

Entrada: str = “ababccc”
Salida: 5
Explicación:
Divide la string dada en las substrings “a”, “b”, “ab”, “c” y “cc”.
Por lo tanto, el recuento máximo de substrings únicas es 5.

Entrada: str = “aba”
Salida: 2

Enfoque: El problema se puede resolver mediante el enfoque Codicioso . Siga los pasos a continuación para resolver el problema: 

1. Inicializa un Set S .
2. Iterar sobre los caracteres de la string str y para cada i y encontrar la substring hasta ese índice.
3. Si la substring dada no está presente en el Set S , insértela para actualizar el conteo máximo y elimínela del Set , porque el mismo carácter no se puede reutilizar.
4. Devuelve el recuento máximo.

A continuación se muestra la implementación del enfoque anterior:

// CPP program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Utility function to find maximum count of
// unique substrings by splitting the string
int maxUnique(string S, set<string> st)
{
 
  // Stores maximum count of unique substring
  // by splitting the string into substrings
  int mx = 0;
 
  // Iterate over the characters of the string
  for (int i = 1; i <= S.length(); i++)
  {
 
    // Stores prefix substring
    string tmp = S.substr(0, i);
 
    // Check if the current substring
    // already exists
    if (st.find(tmp) == st.end())
    {
 
      // Insert tmp into set
      st.insert(tmp);
 
      // Recursively call for remaining
      // characters of string
      mx = max(mx, maxUnique(S.substr(i), st) + 1);
 
      // Remove from the set
      st.erase(tmp);
    }
  }
 
  // Return answer
  return mx;
}
 
 
// Function to find the maximum count of
// unique substrings by splitting a string
// into maximum number of unique substrings
int maxUniqueSplit(string S)
{
  set<string> st;
  return maxUnique(S, st);
}
 
// Driver Code
int main()
{
  string S = "ababccc";
  int res = maxUniqueSplit(S);
 
  cout<<res;
}
 
// This code is contributed by jana_sayantan.

// Java program for the above approach
import java.io.*;
import java.util.*;
class Solution {
 
    // Function to find the maximum count of
    // unique substrings by splitting a string
    // into maximum number of unique substrings
    public int maxUniqueSplit(String S)
    {
        return maxUnique(S, new HashSet<String>());
    }
 
    // Utility function to find maximum count of
    // unique substrings by splitting the string
    public int maxUnique(String S, Set<String> set)
    {
 
        // Stores maximum count of unique substring
        // by splitting the string into substrings
        int max = 0;
 
        // Iterate over the characters of the string
        for (int i = 1; i <= S.length(); i++) {
 
            // Stores prefix substring
            String tmp = S.substring(0, i);
 
            // Check if the current substring
            // already exists
            if (!set.contains(tmp)) {
 
                // Insert tmp into set
                set.add(tmp);
 
                // Recursively call for remaining
                // characters of string
                max = Math.max(max, maxUnique(
                                        S.substring(i), set)
                                        + 1);
 
                // Remove from the set
                set.remove(tmp);
            }
        }
 
        // Return answer
        return max;
    }
}
 
// Driver Code
class GFG {
 
    public static void main(String[] args)
    {
        Solution st = new Solution();
        String S = "ababccc";
        int res = st.maxUniqueSplit(S);
 
        System.out.println(res);
    }
}

# Python3 program for the above approach
 
# Utility function to find maximum count of
# unique substrings by splitting the string
def maxUnique(S):
    global d
 
    # Stores maximum count of unique substring
    # by splitting the string into substrings
    maxm = 0
 
    # Iterate over the characters of the string
    for i in range(1, len(S) + 1):
 
        # Stores prefix substring
        tmp = S[0:i]
 
        # Check if the current substring
        # already exists
        if (tmp not in d):
 
            # Insert tmp into set
            d[tmp] = 1
 
            # Recursively call for remaining
            # characters of string
            maxm = max(maxm, maxUnique(S[i:]) + 1)
 
            # Remove from the set
            del d[tmp]
 
    # Return answer
    return maxm
 
# Driver Code
if __name__ == '__main__':
   
    # Solution st = new Solution()
    S = "ababccc"
    d = {}
    res = maxUnique(S)
    # d = {}
 
    print(res)
 
# This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG {
 
  // Function to find the maximum count of
  // unique substrings by splitting a string
  // into maximum number of unique substrings
  public int maxUniqueSplit(String S)
  {
    return maxUnique(S, new HashSet<String>());
  }
 
  // Utility function to find maximum count of
  // unique substrings by splitting the string
  public int maxUnique(String S, HashSet<String> set)
  {
 
    // Stores maximum count of unique substring
    // by splitting the string into substrings
    int max = 0;
 
    // Iterate over the characters of the string
    for (int i = 1; i <= S.Length; i++) {
 
      // Stores prefix substring
      String tmp = S.Substring(0, i);
 
      // Check if the current substring
      // already exists
      if (!set.Contains(tmp)) {
 
        // Insert tmp into set
        set.Add(tmp);
 
        // Recursively call for remaining
        // characters of string
        max = Math.Max(max, maxUnique(
          S.Substring(i), set)
                       + 1);
 
        // Remove from the set
        set.Remove(tmp);
      }
    }
 
    // Return answer
    return max;
  }
}
 
// Driver Code
public class GFG {
 
  public static void Main(String[] args)
  {
    Solution st = new Solution();
    String S = "ababccc";
    int res = st.maxUniqueSplit(S);
 
    Console.WriteLine(res);
  }
}
 
// This code contributed by shikhasingrajput

<script>
 
// Javascript program for the above approach
 
// Utility function to find maximum count of
// unique substrings by splitting the string
function maxUnique(S, st)
{
 
  // Stores maximum count of unique substring
  // by splitting the string into substrings
  var mx = 0;
 
  // Iterate over the characters of the string
  for (var i = 1; i <= S.length; i++)
  {
 
    // Stores prefix substring
    var tmp = S.substring(0, i);
 
    // Check if the current substring
    // already exists
    if (!st.has(tmp))
    {
 
      // Insert tmp into set
      st.add(tmp);
 
      // Recursively call for remaining
      // characters of string
      mx = Math.max(mx, maxUnique(S.substring(i), st) + 1);
 
      // Remove from the set
      st.delete(tmp);
    }
  }
 
  // Return answer
  return mx;
}
 
 
// Function to find the maximum count of
// unique substrings by splitting a string
// into maximum number of unique substrings
function maxUniqueSplit(S)
{
  var st = new Set();
  return maxUnique(S, st);
}
 
// Driver Code
var S = "ababccc";
var res = maxUniqueSplit(S);
document.write( res);
 
 
</script>

5

Complejidad del Tiempo: O( )

Espacio Auxiliar: O(N)