Longitudes de particiones maximizadas de una string tal que cada carácter de la string aparece en una substring

Posted on by Rudeus Greyrat

Dada la string str de alfabetos en minúsculas, divida la string dada en tantas substrings como sea posible de modo que cada carácter de la string dada aparezca en una sola substring. La tarea es imprimir la longitud de todas esas particiones.

Ejemplos:

Entrada: str = “acbbcc”
Salida: 1 5
Explicación:
Las particiones posibles en las que cada carácter de las strings aparece en una partición como máximo son “a” y “cbbcc”.
Por lo tanto, la longitud es {1, 5}

Entrada: str = “abaccbdeffed”
Salida: 6 6
Explicación:
Las posibles particiones en las que cada carácter de las strings aparece en una partición como máximo son “abaccb” y “deffed”.
Por lo tanto, la longitud es {6, 6}

Enfoque: este problema se puede resolver fácilmente utilizando el enfoque codicioso . Siga los pasos que se indican a continuación para resolver el problema.

  1. Almacene el último índice de todos los caracteres de la string .
  2. Dado que la string contiene solo letras minúsculas , simplemente use una array de tamaño fijo 26 para almacenar los últimos índices de cada carácter.
  3. Itere sobre la string dada y siga los pasos a continuación:
    • Agregue el carácter actual a la partición si la última posición del carácter excede el índice actual y aumente la longitud de la partición.
    • Si el último índice del carácter actual es igual al índice actual, almacene su longitud y continúe con el siguiente carácter y así sucesivamente.
  4. Después de completar los pasos anteriores, imprima todas las longitudes almacenadas.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the length of
// all partitions of a string such
// that each characters occurs in
// a single substring
void partitionString(string s)
{
    int n = s.size();
 
    // Stores last index of string s
    vector<int> ans;
 
    if (n == 0) {
        cout << "-1";
        return;
    }
 
    // Find the last position of
    // each letter in the string
    vector<int> last_pos(26, -1);
 
    for (int i = n - 1; i >= 0; --i) {
 
        // Update the last index
        if (last_pos[s[i] - 'a'] == -1) {
            last_pos[s[i] - 'a'] = i;
        }
    }
 
    int minp = -1, plen = 0;
 
    // Iterate the given string
    for (int i = 0; i < n; ++i) {
 
        // Get the last index of s[i]
        int lp = last_pos[s[i] - 'a'];
 
        // Extend the current partition
        // characters last pos
        minp = max(minp, lp);
 
        // Increase len of partition
        ++plen;
 
        // if the current pos of
        // character equals the min pos
        // then the end of partition
        if (i == minp) {
 
            // Store the length
            ans.push_back(plen);
            minp = -1;
            plen = 0;
        }
    }
 
    // Print all the partition lengths
    for (int i = 0;
         i < (int)ans.size(); i++) {
        cout << ans[i] << " ";
    }
}
 
// Driver Code
int main()
{
    // Given string str
    string str = "acbbcc";
 
    // Function Call
    partitionString(str);
 
    return 0;
}

Java

// Java program for
// the above approach
import java.util.*;
class GFG{
 
// Function to find the length of
// all partitions of a String such
// that each characters occurs in
// a single subString
static void partitionString(String s)
{
  int n = s.length();
 
  // Stores last index of String s
  Vector<Integer> ans =
         new Vector<Integer>();
 
  if (n == 0)
  {
    System.out.print("-1");
    return;
  }
 
  // Find the last position of
  // each letter in the String
  int []last_pos = new int[26];
  Arrays.fill(last_pos, -1);
 
  for (int i = n - 1; i >= 0; --i)
  {
    // Update the last index
    if (last_pos[s.charAt(i) - 'a'] == -1)
    {
      last_pos[s.charAt(i) - 'a'] = i;
    }
  }
 
  int minp = -1, plen = 0;
 
  // Iterate the given String
  for (int i = 0; i < n; ++i)
  {
    // Get the last index of s[i]
    int lp = last_pos[s.charAt(i) - 'a'];
 
    // Extend the current partition
    // characters last pos
    minp = Math.max(minp, lp);
 
    // Increase len of partition
    ++plen;
 
    // if the current pos of
    // character equals the min pos
    // then the end of partition
    if (i == minp)
    {
      // Store the length
      ans.add(plen);
      minp = -1;
      plen = 0;
    }
  }
 
  // Print all the partition lengths
  for (int i = 0; i < (int)ans.size(); i++)
  {
    System.out.print(ans.get(i) + " ");
  }
}
 
// Driver Code
public static void main(String[] args)
{
  // Given String str
  String str = "acbbcc";
 
  // Function Call
  partitionString(str);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program for the above approach
 
# Function to find the length of
# all partitions of a string such
# that each characters occurs in
# a single substring
def partitionString(s):
     
    n = len(s)
 
    # Stores last index of string s
    ans = []
 
    if (n == 0):
        print("-1")
        return
     
    # Find the last position of
    # each letter in the string
    last_pos = [-1] * 26
 
    for i in range(n - 1 , -1 , -1):
 
        # Update the last index
        if (last_pos[ord(s[i]) - ord('a')] == -1):
            last_pos[ord(s[i]) - ord('a')] = i
     
    minp = -1
    plen = 0
 
    # Iterate the given string
    for i in range(n):
 
        # Get the last index of s[i]
        lp = last_pos[ord(s[i]) - ord('a')]
 
        # Extend the current partition
        # characters last pos
        minp = max(minp, lp)
 
        # Increase len of partition
        plen += 1
 
        # if the current pos of
        # character equals the min pos
        # then the end of partition
        if (i == minp):
 
            # Store the length
            ans.append(plen)
            minp = -1
            plen = 0
         
    # Print all the partition lengths
    for i in range(len(ans)):
        print(ans[i], end = " ")
 
# Driver Code
 
# Given string str
str = "acbbcc"
 
# Function call
partitionString(str)
 
# This code is contributed by code_hunt

C#

// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to find the length of
// all partitions of a String such
// that each characters occurs in
// a single subString
static void partitionString(String s)
{
  int n = s.Length;
 
  // Stores last index of String s
  List<int> ans = new List<int>();
 
  if (n == 0)
  {
    Console.Write("-1");
    return;
  }
 
  // Find the last position of
  // each letter in the String
  int []last_pos = new int[26];
  for (int i = 0; i < 26; ++i)
  {
    last_pos[i] = -1; 
  }
 
  for (int i = n - 1; i >= 0; --i)
  {
    // Update the last index
    if (last_pos[s[i] - 'a'] == -1)
    {
      last_pos[s[i] - 'a'] = i;
    }
  }
 
  int minp = -1, plen = 0;
 
  // Iterate the given String
  for (int i = 0; i < n; ++i)
  {
    // Get the last index of s[i]
    int lp = last_pos[s[i] - 'a'];
 
    // Extend the current partition
    // characters last pos
    minp = Math.Max(minp, lp);
 
    // Increase len of partition
    ++plen;
 
    // if the current pos of
    // character equals the min pos
    // then the end of partition
    if (i == minp)
    {
      // Store the length
      ans.Add(plen);
      minp = -1;
      plen = 0;
    }
  }
 
  // Print all the partition lengths
  for (int i = 0; i < (int)ans.Count; i++)
  {
    Console.Write(ans[i] + " ");
  }
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given String str
  String str = "acbbcc";
 
  // Function Call
  partitionString(str);
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
// javascript program for the
// above approach
 
// Function to find the length of
// all partitions of a String such
// that each characters occurs in
// a single subString
function partitionString(s)
{
  let n = s.length;
  
  // Stores last index of String s
  let ans = [];
  
  if (n == 0)
  {
    document.write("-1");
    return;
  }
  
  // Find the last position of
  // each letter in the String
  let last_pos = Array(26).fill(-1);
  
  for (let i = n - 1; i >= 0; --i)
  {
    // Update the last index
    if (last_pos[s[i].charCodeAt() - 'a'.charCodeAt()] == -1)
    {
      last_pos[s[i].charCodeAt() - 'a'.charCodeAt()] = i;
    }
  }
  
  let minp = -1, plen = 0;
  
  // Iterate the given String
  for (let i = 0; i < n; ++i)
  {
    // Get the last index of s[i]
    let lp = last_pos[s[i].charCodeAt() - 'a'.charCodeAt()];
  
    // Extend the current partition
    // characters last pos
    minp = Math.max(minp, lp);
  
    // Increase len of partition
    ++plen;
  
    // if the current pos of
    // character equals the min pos
    // then the end of partition
    if (i == minp)
    {
      // Store the length
      ans.push(plen);
      minp = -1;
      plen = 0;
    }
  }
  
  // Print all the partition lengths
  for (let i = 0; i < ans.length; i++)
  {
    document.write(ans[i] + " ");
  }
}
    
  
// Driver Code
 
     // Given String str
  let str = "acbbcc";
  
  // Function Call
  partitionString(str);
 
// This code is contributed by avijitmondal1998.
</script>
Producción: 

1 5

Complejidad temporal: O(N) 
Espacio auxiliar: O(N) 

Publicación traducida automáticamente

Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *