Dada una string str , la tarea es encontrar el recuento de caracteres distintos en todas las substrings distintas de la string dada.
Ejemplos:
Entrada: str = “ABCA”
Salida: 18
Substrings distintas Personajes distintos A 1 AB 2 A B C 3 ABCA 3 B 1 antes de Cristo 2 BCA 3 C 1 California 2 Por lo tanto, 1 + 2 + 3 + 3 + 1 + 2 + 3 + 1 + 2 = 18
Entrada: str = “AAAB”
Salida: 10
Enfoque: tome todas las substrings posibles de la string dada y use un conjunto para verificar si la substring actual se ha procesado antes. Ahora, para cada substring distinta, cuente los caracteres distintos en ella (nuevamente se puede usar set para hacerlo). La suma de este recuento de todas las substrings distintas es la respuesta final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of distinct
// characters in all the distinct
// sub-strings of the given string
int countTotalDistinct(string str)
{
int cnt = 0;
// To store all the sub-strings
set<string> items;
for (int i = 0; i < str.length(); ++i) {
// To store the current sub-string
string temp = "";
// To store the characters of the
// current sub-string
set<char> ans;
for (int j = i; j < str.length(); ++j) {
temp = temp + str[j];
ans.insert(str[j]);
// If current sub-string hasn't
// been stored before
if (items.find(temp) == items.end()) {
// Insert it into the set
items.insert(temp);
// Update the count of
// distinct characters
cnt += ans.size();
}
}
}
return cnt;
}
// Driver code
int main()
{
string str = "ABCA";
cout << countTotalDistinct(str);
return 0;
}
Java
// Java implementation of the approach
import java.util.HashSet;
class geeks
{
// Function to return the count of distinct
// characters in all the distinct
// sub-strings of the given string
public static int countTotalDistinct(String str)
{
int cnt = 0;
// To store all the sub-strings
HashSet<String> items = new HashSet<>();
for (int i = 0; i < str.length(); ++i)
{
// To store the current sub-string
String temp = "";
// To store the characters of the
// current sub-string
HashSet<Character> ans = new HashSet<>();
for (int j = i; j < str.length(); ++j)
{
temp = temp + str.charAt(j);
ans.add(str.charAt(j));
// If current sub-string hasn't
// been stored before
if (!items.contains(temp))
{
// Insert it into the set
items.add(temp);
// Update the count of
// distinct characters
cnt += ans.size();
}
}
}
return cnt;
}
// Driver code
public static void main(String[] args)
{
String str = "ABCA";
System.out.println(countTotalDistinct(str));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 implementation of the approach # Function to return the count of distinct # characters in all the distinct # sub-strings of the given string def countTotalDistinct(string) : cnt = 0; # To store all the sub-strings items = set(); for i in range(len(string)) : # To store the current sub-string temp = ""; # To store the characters of the # current sub-string ans = set(); for j in range(i, len(string)) : temp = temp + string[j]; ans.add(string[j]); # If current sub-string hasn't # been stored before if temp not in items : # Insert it into the set items.add(temp); # Update the count of # distinct characters cnt += len(ans); return cnt; # Driver code if __name__ == "__main__" : string = "ABCA"; print(countTotalDistinct(string)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class geeks
{
// Function to return the count of distinct
// characters in all the distinct
// sub-strings of the given string
public static int countTotalDistinct(String str)
{
int cnt = 0;
// To store all the sub-strings
HashSet<String> items = new HashSet<String>();
for (int i = 0; i < str.Length; ++i)
{
// To store the current sub-string
String temp = "";
// To store the characters of the
// current sub-string
HashSet<char> ans = new HashSet<char>();
for (int j = i; j < str.Length; ++j)
{
temp = temp + str[j];
ans.Add(str[j]);
// If current sub-string hasn't
// been stored before
if (!items.Contains(temp))
{
// Insert it into the set
items.Add(temp);
// Update the count of
// distinct characters
cnt += ans.Count;
}
}
}
return cnt;
}
// Driver code
public static void Main(String[] args)
{
String str = "ABCA";
Console.WriteLine(countTotalDistinct(str));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// js implementation of the approach
// Function to return the count of distinct
// characters in all the distinct
// sub-strings of the given string
function countTotalDistinct(str)
{
let cnt = 0;
// To store all the sub-strings
let items = new Set();
for (let i = 0; i < str.length; ++i) {
// To store the current sub-string
let temp = "";
// To store the characters of the
// current sub-string
let ans = new Set();
for (let j = i; j < str.length; ++j) {
temp = temp + str[j];
ans.add(str[j]);
// If current sub-string hasn't
// been stored before
if (!items.has(temp)) {
// Insert it into the set
items.add(temp);
// Update the count of
// distinct characters
cnt += ans.size;
}
}
}
return cnt;
}
// Driver code
let str = "ABCA";
document.write(countTotalDistinct(str));
</script>
Producción:
18
Complejidad del tiempo: O(n^2)
Como se usa el bucle anidado, la complejidad es orden si n ^ 2
Complejidad espacial: O(n)
Se utilizan dos conjuntos de tamaño n, por lo que la complejidad sería O(2n) nada más que O(n).
Publicación traducida automáticamente
Artículo escrito por Chandan_Agrawal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA