Dada la string str de tamaño N , la tarea es imprimir el número de substrings formadas después del máximo de particiones posibles de modo que no haya dos substrings que tengan un carácter común.
Ejemplos:
Entrada: str = “ababcbacadefegdehijhklij”
Salida: 3
Explicación:
Particionar en el índice 8 y en el 15 produce tres substrings “ababcbaca”, “defegde” y “hijhklij” tales que ninguna de ellas tiene un carácter común. Entonces, el máximo de particiones es 3.
Entrada: str = “aaa”
Salida: 1
Explicación:
Dado que la string consta de un solo carácter, no se puede realizar ninguna partición.
Acercarse:
- Encuentre el último índice de cada carácter único desde el final de la string y guárdelo en un mapa .
- Recorra la array desde el índice 0 hasta el último índice y cree una variable separada para almacenar el índice final de la partición.
- Recorra cada variable en la string y verifique si el final de la partición, indicado por el índice de str[i] almacenado en el mapa, es mayor que el final anterior. Si es así, actualízalo.
- Compruebe si la variable actual supera el final de la partición. Significa que se encontró la primera partición. Actualice el final de la partición a max(k, mp[str[i]]) .
- Recorra toda la string y use un proceso similar para encontrar la siguiente partición y así sucesivamente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the
// maximum number of
// partitions possible such
// that no two substrings
// have common character
#include
using namespace std;
// Function to calculate and return
// the maximum number of partitions
int maximum_partition(string str)
{
// r: Stores the maximum number
// of partitions
// k: Stores the ending index
// of the partition
int i = 0, j = 0, k = 0;
int c = 0, r = 0;
// Stores the last index
// of every unique character
// of the string
unordered_map m;
// Traverse the string and
// store the last index
// of every character
for (i = str.length() - 1;
i >= 0;
i--) {
if (m[str[i]] == 0) {
m[str[i]] = i;
}
}
i = 0;
// Store the last index of the
// first character from map
k = m[str[i]];
for (i = 0; i < str.length(); i++) {
if (i <= k) {
c = c + 1;
// Update K to find
// the end of partition
k = max(k, m[str[i]]);
}
// Otherwise, the end of
// partition is found
else {
// Increment r
r = r + 1;
c = 1;
// Update k for the
// next partition
k = max(k, m[str[i]]);
}
}
// Add the last partition
if (c != 0) {
r = r + 1;
}
return r;
}
// Driver Program
int main()
{
string str
= "ababcbacadefegdehijhklij";
cout << maximum_partition(str);
}
Java
// Java program to find the
// maximum number of
// partitions possible such
// that no two subStrings
// have common character
import java.util.*;
class GFG{
// Function to calculate and return
// the maximum number of partitions
static int maximum_partition(String str)
{
// r: Stores the maximum number
// of partitions
// k: Stores the ending index
// of the partition
int i = 0, j = 0, k = 0;
int c = 0, r = 0;
// Stores the last index
// of every unique character
// of the String
HashMap<Character,
Integer> m = new HashMap<>();
// Traverse the String and
// store the last index
// of every character
for (i = str.length() - 1;
i >= 0; i--)
{
if (!m.containsKey(str.charAt(i)))
{
m.put(str.charAt(i), i);
}
}
i = 0;
// Store the last index of the
// first character from map
k = m.get(str.charAt(i));
for (i = 0; i < str.length(); i++)
{
if (i <= k)
{
c = c + 1;
// Update K to find
// the end of partition
k = Math.max(k, m.get(str.charAt(i)));
}
// Otherwise, the end of
// partition is found
else
{
// Increment r
r = r + 1;
c = 1;
// Update k for the
// next partition
k = Math.max(k, m.get(str.charAt(i)));
}
}
// Add the last
// partition
if (c != 0)
{
r = r + 1;
}
return r;
}
// Driver code
public static void main(String[] args)
{
String str = "ababcbacadefegdehijhklij";
System.out.print(maximum_partition(str));
}
}
// This code is contributed by Princi Singh
Python 3
# Python3 program to find the
# maximum number of
# partitions possible such
# that no two substrings
# have common character
# Function to calculate and return
# the maximum number of partitions
def maximum_partition(strr):
# r: Stores the maximum number
# of partitions
# k: Stores the ending index
# of the partition
i = 0
j = 0
k = 0
c = 0
r = 0
# Stores the last index
# of every unique character
# of the string
m = {}
# Traverse the and
# store the last index
# of every character
for i in range(len(strr) - 1, -1, -1):
if (strr[i] not in m):
m[strr[i]] = i
i = 0
# Store the last index of the
# first character from map
k = m[strr[i]]
for i in range(len(strr)):
if (i <= k):
c = c + 1
# Update K to find
# the end of partition
k = max(k, m[strr[i]])
# Otherwise, the end of
# partition is found
else:
# Increment r
r = r + 1
c = 1
# Update k for the
# next partition
k = max(k, m[strr[i]])
# Add the last partition
if (c != 0):
r = r + 1
return r
# Driver Code
if __name__ == '__main__':
strr = "ababcbacadefegdehijhklij"
print(maximum_partition(strr))
# This code is contributed by Mohit Kumar
C#
// C# program to find the
// maximum number of
// partitions possible such
// that no two subStrings
// have common character
using System;
using System.Collections.Generic;
class GFG{
// Function to calculate and return
// the maximum number of partitions
static int maximum_partition(String str)
{
// r: Stores the maximum number
// of partitions
// k: Stores the ending index
// of the partition
int i = 0, j = 0, k = 0;
int c = 0, r = 0;
// Stores the last index
// of every unique character
// of the String
Dictionary<char,
int> m = new Dictionary<char,
int>();
// Traverse the String and
// store the last index
// of every character
for (i = str.Length - 1;
i >= 0; i--)
{
if (!m.ContainsKey(str[i]))
{
m.Add(str[i], i);
}
}
i = 0;
// Store the last index of the
// first character from map
k = m[str[i]];
for (i = 0; i < str.Length; i++)
{
if (i <= k)
{
c = c + 1;
// Update K to find
// the end of partition
k = Math.Max(k, m[str[i]]);
}
// Otherwise, the end of
// partition is found
else
{
// Increment r
r = r + 1;
c = 1;
// Update k for the
// next partition
k = Math.Max(k, m[str[i]]);
}
}
// Add the last
// partition
if (c != 0)
{
r = r + 1;
}
return r;
}
// Driver code
public static void Main(String[] args)
{
String str = "ababcbacadefegdehijhklij";
Console.Write(maximum_partition(str));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program to find the
// maximum number of
// partitions possible such
// that no two substrings
// have common character
// Function to calculate and return
// the maximum number of partitions
function maximum_partition( str)
{
// r: Stores the maximum number
// of partitions
// k: Stores the ending index
// of the partition
var i = 0, j = 0, k = 0;
var c = 0, r = 0;
// Stores the last index
// of every unique character
// of the string
var m = new Map();
// Traverse the string and
// store the last index
// of every character
for (i = str.length - 1;
i >= 0;
i--) {
if (!m.has(str[i])) {
m.set(str[i],i);
}
}
i = 0;
// Store the last index of the
// first character from map
k = m.get(str[i]);
for (i = 0; i < str.length; i++) {
if (i <= k) {
c = c + 1;
// Update K to find
// the end of partition
k = Math.max(k, m.get(str[i]));
}
// Otherwise, the end of
// partition is found
else {
// Increment r
r = r + 1;
c = 1;
// Update k for the
// next partition
k = Math.max(k, m.get(str[i]));
}
}
// Add the last partition
if (c != 0) {
r = r + 1;
}
return r;
}
// Driver Program
var str
= "ababcbacadefegdehijhklij";
document.write( maximum_partition(str));
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por vabzcode12 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA