Dada una string str , la tarea es encontrar la cantidad máxima de caracteres comunes que no se repiten que se pueden obtener dividiendo la string dada en dos substrings no vacías .
Ejemplos:
Entrada: str = “aabbca”
Salida: 2
Explicación: Particione la string en dos substrings { { str[0], … str[2] }, { str [
3], …, str[5] } }
los caracteres repetidos presentes en ambas substrings son { ‘a’, ‘b’}
Por lo tanto, la salida requerida es 2.Entrada: str = “aaaaaaaaaa”
Salida: 1
Enfoque ingenuo: el enfoque más simple para resolver este problema es iterar sobre los caracteres de la string y dividir la string en dos substrings no vacías en todos los índices posibles y contar la cantidad de caracteres repetidos comunes de las dos substrings. Imprime el conteo máximo obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count maximum common non-repeating
// characters that can be obtained by partitioning
// the string into two non-empty substrings
int countCommonChar(int ind, string& S)
{
// Stores count of non-repeating characters
// present in both the substrings
int cnt = 0;
// Stores distinct characters
// in left substring
set<char> ls;
// Stores distinct characters
// in right substring
set<char> rs;
// Traverse left substring
for (int i = 0; i < ind; ++i) {
// Insert S[i] into ls
ls.insert(S[i]);
}
// Traverse right substring
for (int i = ind; i < S.length();
++i) {
// Insert S[i] into rs
rs.insert(S[i]);
}
// Traverse distinct characters
// of left substring
for (auto v : ls) {
// If current character is
// present in right substring
if (rs.count(v)) {
// Update cnt
++cnt;
}
}
// Return count
return cnt;
}
// Function to partition the string into
// two non-empty substrings in all possible ways
void partitionStringWithMaxCom(string& S)
{
// Stores maximum common distinct characters
// present in both the substring partitions
int ans = 0;
// Traverse the string
for (int i = 1; i < S.length(); ++i) {
// Update ans
ans = max(ans,
countCommonChar(i, S));
}
// Print count of maximum common
// non-repeating characters
cout << ans << "\n";
}
// Driver Code
int main()
{
string str = "aabbca";
partitionStringWithMaxCom(str);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to count maximum common non-repeating
// characters that can be obtained by partitioning
// the String into two non-empty subStrings
static int countCommonChar(int ind, String S)
{
// Stores count of non-repeating characters
// present in both the subStrings
int cnt = 0;
// Stores distinct characters
// in left subString
HashSet<Character> ls = new HashSet<Character>();
// Stores distinct characters
// in right subString
HashSet<Character> rs = new HashSet<Character>();
// Traverse left subString
for (int i = 0; i < ind; ++i) {
// Insert S[i] into ls
ls.add(S.charAt(i));
}
// Traverse right subString
for (int i = ind; i < S.length();
++i) {
// Insert S[i] into rs
rs.add(S.charAt(i));
}
// Traverse distinct characters
// of left subString
for (char v : ls) {
// If current character is
// present in right subString
if (rs.contains(v)) {
// Update cnt
++cnt;
}
}
// Return count
return cnt;
}
// Function to partition the String into
// two non-empty subStrings in all possible ways
static void partitionStringWithMaxCom(String S)
{
// Stores maximum common distinct characters
// present in both the subString partitions
int ans = 0;
// Traverse the String
for (int i = 1; i < S.length(); ++i) {
// Update ans
ans = Math.max(ans,
countCommonChar(i, S));
}
// Print count of maximum common
// non-repeating characters
System.out.print(ans+ "\n");
}
// Driver Code
public static void main(String[] args)
{
String str = "aabbca";
partitionStringWithMaxCom(str);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement # the above approach # Function to count maximum common # non-repeating characters that can # be obtained by partitioning the # string into two non-empty substrings def countCommonChar(ind, S): # Stores count of non-repeating # characters present in both the # substrings cnt = 0 # Stores distinct characters # in left substring ls = set() # Stores distinct characters # in right substring rs = set() # Traverse left substring for i in range(ind): # Insert S[i] into ls ls.add(S[i]) # Traverse right substring for i in range(ind, len(S)): # Insert S[i] into rs rs.add(S[i]) # Traverse distinct characters # of left substring for v in ls: # If current character is # present in right substring if v in rs: # Update cnt cnt += 1 # Return count return cnt # Function to partition the string # into two non-empty substrings in # all possible ways def partitionStringWithMaxCom(S): # Stores maximum common distinct # characters present in both the # substring partitions ans = 0 # Traverse the string for i in range(1, len(S)): # Update ans ans = max(ans, countCommonChar(i, S)) # Print count of maximum common # non-repeating characters print(ans) # Driver Code if __name__ == "__main__": string = "aabbca" partitionStringWithMaxCom(string) # This code is contributed by AnkThon
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to count maximum common non-repeating
// characters that can be obtained by partitioning
// the String into two non-empty subStrings
static int countCommonChar(int ind, String S)
{
// Stores count of non-repeating characters
// present in both the subStrings
int cnt = 0;
// Stores distinct characters
// in left subString
HashSet<char> ls = new HashSet<char>();
// Stores distinct characters
// in right subString
HashSet<char> rs = new HashSet<char>();
// Traverse left subString
for(int i = 0; i < ind; ++i)
{
// Insert S[i] into ls
ls.Add(S[i]);
}
// Traverse right subString
for(int i = ind; i < S.Length; ++i)
{
// Insert S[i] into rs
rs.Add(S[i]);
}
// Traverse distinct characters
// of left subString
foreach(char v in ls)
{
// If current character is
// present in right subString
if (rs.Contains(v))
{
// Update cnt
++cnt;
}
}
// Return count
return cnt;
}
// Function to partition the String into
// two non-empty subStrings in all possible ways
static void partitionStringWithMaxCom(String S)
{
// Stores maximum common distinct characters
// present in both the subString partitions
int ans = 0;
// Traverse the String
for(int i = 1; i < S.Length; ++i)
{
// Update ans
ans = Math.Max(ans,
countCommonChar(i, S));
}
// Print count of maximum common
// non-repeating characters
Console.Write(ans + "\n");
}
// Driver Code
public static void Main(String[] args)
{
String str = "aabbca";
partitionStringWithMaxCom(str);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to count maximum common non-repeating
// characters that can be obtained by partitioning
// the string into two non-empty substrings
function countCommonChar(ind, S)
{
// Stores count of non-repeating characters
// present in both the substrings
var cnt = 0;
// Stores distinct characters
// in left substring
var ls = new Set();
// Stores distinct characters
// in right substring
var rs = new Set();
// Traverse left substring
for (var i = 0; i < ind; ++i) {
// Insert S[i] into ls
ls.add(S[i]);
}
// Traverse right substring
for (var i = ind; i < S.length;
++i) {
// Insert S[i] into rs
rs.add(S[i]);
}
// Traverse distinct characters
// of left substring
ls.forEach(v => {
// If current character is
// present in right substring
if (rs.has(v)) {
// Update cnt
++cnt;
}
});
// Return count
return cnt;
}
// Function to partition the string into
// two non-empty substrings in all possible ways
function partitionStringWithMaxCom(S)
{
// Stores maximum common distinct characters
// present in both the substring partitions
var ans = 0;
// Traverse the string
for (var i = 1; i < S.length; ++i) {
// Update ans
ans = Math.max(ans,
countCommonChar(i, S));
}
// Print count of maximum common
// non-repeating characters
document.write( ans);
}
// Driver Code
var str = "aabbca";
partitionStringWithMaxCom(str);
</script>
Producción
2
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar Hashing y Ordered Set para almacenar los distintos caracteres de la string en orden. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos res , para almacenar el recuento máximo de caracteres distintos comunes presentes en ambas substrings dividiendo la string en dos substrings.
- Inicialice un mapa , digamos mp , para almacenar la frecuencia de cada carácter distinto de la string .
- Inicialice un conjunto ordenado , digamos Q , para almacenar los distintos caracteres de la string en orden ordenado.
- Iterar sobre los caracteres de la string y para cada i- ésimo carácter, disminuir la frecuencia de str[i] y verificar si la frecuencia de mp[str[i]] es igual a 0 o no. Si se encuentra que es falso, elimine str[i] del conjunto ordenado .
- De lo contrario, inserte str[i] en el conjunto ordenado y actualice res = max(res, X) , donde X es el recuento de elementos en el conjunto ordenado.
- Finalmente, imprima el valor de res .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update>;
// Function to count maximum common non-repeating
// characters that can be obtained by partitioning
// the string into two non-empty substrings
int countMaxCommonChar(string& S)
{
// Stores distinct characters
// of S in sorted order
ordered_set<char> Q;
// Stores maximum common distinct characters
// present in both the partitions
int res = 0;
// Stores frequency of each
// distinct character n the string S
map<char, int> freq;
// Traverse the string
for (int i = 0; i < S.length(); i++) {
// Update frequency of S[i]
freq[S[i]]++;
}
// Traverse the string
for (int i = 0; i < S.length(); i++) {
// Decreasing frequency of S[i]
freq[S[i]]--;
// If the frequency of S[i] is 0
if (!freq[S[i]]) {
// Remove S[i] from Q
Q.erase(S[i]);
}
else {
// Insert S[i] into Q
Q.insert(S[i]);
}
// Stores count of distinct
// characters in Q
int curr = Q.size();
// Update res
res = max(res, curr);
}
cout << res << "\n";
}
// Driver Code
int main()
{
string str = "aabbca";
// Function call
countMaxCommonChar(str);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to count maximum common non-repeating
// characters that can be obtained by partitioning
// the String into two non-empty subStrings
static void countMaxCommonChar(char[] S)
{
// Stores distinct characters
// of S in sorted order
LinkedHashSet<Character> Q = new LinkedHashSet<>();
// Stores maximum common distinct characters
// present in both the partitions
int res = 1;
// Stores frequency of each
// distinct character n the String S
HashMap<Character, Integer> freq = new HashMap<>();
// Traverse the String
for(int i = 0; i < S.length; i++)
{
// Update frequency of S[i]
if (freq.containsKey(S[i]))
{
freq.put(S[i], freq.get(S[i]) + 1);
}
else
{
freq.put(S[i], 1);
}
}
// Traverse the String
for(int i = 0; i < S.length; i++)
{
// Decreasing frequency of S[i]
if (freq.containsKey(S[i]))
{
freq.put(S[i], freq.get(S[i]) - 1);
}
// If the frequency of S[i] is 0
if (!freq.containsKey(S[i]))
{
// Remove S[i] from Q
Q.remove(S[i]);
}
else
{
// Insert S[i] into Q
Q.add(S[i]);
}
// Stores count of distinct
// characters in Q
int curr = Q.size() - 1;
// Update res
res = Math.max(res, curr);
}
System.out.print(res + "\n");
}
// Driver Code
public static void main(String[] args)
{
String str = "aabbca";
// Function call
countMaxCommonChar(str.toCharArray());
}
}
// This code is contributed by aashish1995
Producción
2
Complejidad de tiempo: O(N * log(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