Dada una string str que consta de caracteres en minúsculas, la tarea es encontrar el número total de substrings únicas con caracteres que no se repiten.
Ejemplos:
Entrada: str = “abba”
Salida: 4
Explicación:
Hay 4 substrings únicas. Son: “a”, “ab”, “b”, “ba”.
Entrada: str = “acbacbacaa”
Salida: 10
Enfoque: la idea es iterar sobre todas las substrings . Para cada substring, verifique si cada carácter en particular se ha producido previamente o no. Si es así, aumente la cantidad de substrings requeridas. Al final, devuelva este recuento como el recuento de todas las substrings únicas con caracteres que no se repiten.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to find the count of
// all unique sub-strings with
// non-repeating characters
#include <bits/stdc++.h>
using namespace std;
// Function to count all unique
// distinct character substrings
int distinctSubstring(string& P, int N)
{
// Hashmap to store all substrings
unordered_set<string> S;
// Iterate over all the substrings
for (int i = 0; i < N; ++i) {
// Boolean array to maintain all
// characters encountered so far
vector<bool> freq(26, false);
// Variable to maintain the
// substring till current position
string s;
for (int j = i; j < N; ++j) {
// Get the position of the
// character in the string
int pos = P[j] - 'a';
// Check if the character is
// encountred
if (freq[pos] == true)
break;
freq[pos] = true;
// Add the current character
// to the substring
s += P[j];
// Insert substring in Hashmap
S.insert(s);
}
}
return S.size();
}
// Driver code
int main()
{
string S = "abba";
int N = S.length();
cout << distinctSubstring(S, N);
return 0;
}
Java
// Java program to find the count of
// all unique sub-Strings with
// non-repeating characters
import java.util.*;
class GFG{
// Function to count all unique
// distinct character subStrings
static int distinctSubString(String P, int N)
{
// Hashmap to store all subStrings
HashSet<String> S = new HashSet<String>();
// Iterate over all the subStrings
for (int i = 0; i < N; ++i) {
// Boolean array to maintain all
// characters encountered so far
boolean []freq = new boolean[26];
// Variable to maintain the
// subString till current position
String s = "";
for (int j = i; j < N; ++j) {
// Get the position of the
// character in the String
int pos = P.charAt(j) - 'a';
// Check if the character is
// encountred
if (freq[pos] == true)
break;
freq[pos] = true;
// Add the current character
// to the subString
s += P.charAt(j);
// Insert subString in Hashmap
S.add(s);
}
}
return S.size();
}
// Driver code
public static void main(String[] args)
{
String S = "abba";
int N = S.length();
System.out.print(distinctSubString(S, N));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find the count of
# all unique sub-strings with
# non-repeating characters
# Function to count all unique
# distinct character substrings
def distinctSubstring(P, N):
# Hashmap to store all substrings
S = dict()
# Iterate over all the substrings
for i in range(N):
# Boolean array to maintain all
# characters encountered so far
freq = [False]*26
# Variable to maintain the
# substring till current position
s = ""
for j in range(i,N):
# Get the position of the
# character in the string
pos = ord(P[j]) - ord('a')
# Check if the character is
# encountred
if (freq[pos] == True):
break
freq[pos] = True
# Add the current character
# to the substring
s += P[j]
# Insert substring in Hashmap
S[s] = 1
return len(S)
# Driver code
S = "abba"
N = len(S)
print(distinctSubstring(S, N))
# This code is contributed by mohit kumar 29
C#
// C# program to find the count of
// all unique sub-Strings with
// non-repeating characters
using System;
using System.Collections.Generic;
class GFG{
// Function to count all unique
// distinct character subStrings
static int distinctSubString(String P, int N)
{
// Hashmap to store all subStrings
HashSet<String> S = new HashSet<String>();
// Iterate over all the subStrings
for (int i = 0; i < N; ++i) {
// Boolean array to maintain all
// characters encountered so far
bool []freq = new bool[26];
// Variable to maintain the
// subString till current position
String s = "";
for (int j = i; j < N; ++j) {
// Get the position of the
// character in the String
int pos = P[j] - 'a';
// Check if the character is
// encountred
if (freq[pos] == true)
break;
freq[pos] = true;
// Add the current character
// to the subString
s += P[j];
// Insert subString in Hashmap
S.Add(s);
}
}
return S.Count;
}
// Driver code
public static void Main(String[] args)
{
String S = "abba";
int N = S.Length;
Console.Write(distinctSubString(S, N));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to find the count of
// all unique sub-strings with
// non-repeating characters
// Function to count all unique
// distinct character substrings
function distinctSubstring(P, N)
{
// Hashmap to store all substrings
var S = new Set();
// Iterate over all the substrings
for (var i = 0; i < N; ++i) {
// Boolean array to maintain all
// characters encountered so far
var freq = Array(26).fill(false);
// Variable to maintain the
// substring till current position
var s = "";
for (var j = i; j < N; ++j) {
// Get the position of the
// character in the string
var pos = P[j].charCodeAt(0) - 'a'.charCodeAt(0);
// Check if the character is
// encountred
if (freq[pos] == true)
break;
freq[pos] = true;
// Add the current character
// to the substring
s += P[j];
// Insert substring in Hashmap
S.add(s);
}
}
return S.size;
}
// Driver code
var S = "abba";
var N = S.length;
document.write( distinctSubstring(S, N));
</script>
Producción:
4
Complejidad de tiempo: O(N 2 ) donde N es la longitud de la string.
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA