Encuentra caracteres distintos en substrings distintas de una string

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++ 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 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 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# 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

<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>

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).