Dado un número N muy grande en forma de string y un número K , la tarea es imprimir todos los números repetidos de K dígitos cuya frecuencia sea mayor que 1.
Ejemplos:
Entrada: str = “123412345123456”, K = 4
Salida:
1234 – 3
2345 – 2
Explicación:
Los números de 4 dígitos que tienen una frecuencia mayor que 1 son 1234 y 2345.Entrada: N = 1432543214325432, K = 5
Salida:
14325 – 2
32543 – 2
43254 – 2
Explicación:
Los números de 5 dígitos que tienen una frecuencia mayor que 1 son 14325, 32543 y 43254.
Enfoque: dado que el número se da en forma de string, la idea es almacenar todas las substrings de tamaño K en un mapa con su frecuencia. Ahora, mientras itera el Mapa, imprime solo aquellas substrings que tienen una frecuencia mayor que uno junto con la cantidad de veces que aparecen.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print all K digit
// repeating numbers
void print_Kdigit(string S, int K)
{
// Map to store the substrings
// with their frequencies
map<string, int> m;
// Iterate over every substring
// and store their frequencies
// in the map
for (int i = 0; i < S.length() - K;
i++) {
string a = S.substr(i, K);
// Increment the count of
// substrings in map
m[a]++;
}
// Iterate over all the substrings
// present in the map
for (auto x : m) {
// Condition to check if the
// frequency of the substring
// present in the map
// is greater than 1
if (x.second > 1) {
cout << x.first << " - "
<< x.second << "\n";
}
}
}
// Driver Code
int main()
{
// Given Number in form of string
string str = "123412345123456";
// Given K
int K = 4;
// Function Call
print_Kdigit(str, K);
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to print all K digit
// repeating numbers
static void print_Kdigit(String S, int K)
{
// Map to store the substrings
// with their frequencies
Map<String, Integer> m = new HashMap<>();
// Iterate over every substring
// and store their frequencies
// in the map
for(int i = 0; i < S.length() - K; i++)
{
String a = S.substring(i, i + K);
// Increment the count of
// substrings in map
m.put(a, m.getOrDefault(a, 0) + 1);
}
// Iterate over all the substrings
// present in the map
for(Map.Entry<String, Integer> x : m.entrySet())
{
// Condition to check if the
// frequency of the substring
// present in the map
// is greater than 1
if (x.getValue() > 1)
{
System.out.println(x.getKey() + " - " +
x.getValue());
}
}
}
// Driver code
public static void main(String[] args)
{
// Given Number in form of string
String str = "123412345123456";
// Given K
int K = 4;
// Function call
print_Kdigit(str, K);
}
}
// This code is contributed by offbeat
Python3
# Python3 program of the above approach
def print_Kdigit(S, K):
# Dictionary to store the substrings
# with their frequencies
m = {}
# Iterate over every substring
# and store their frequencies
# in the dictionary
for i in range(len(S) - K):
a = S[i:i + K]
# Initialize the count of
# substrings in dictionary with 0
m[a] = 0
for i in range(len(S) - K):
a = S[i:i + K]
# Increment the count of
# substrings in dictionary
m[a] += 1
# Iterate over all the substrings
# present in the dictionary
for key, value in m.items():
if value > 1:
print(key, "-", value)
# Driver Code
str = "123412345123456"
# Given K
K = 4
# Function Call
print_Kdigit(str, K)
# This code is contributed by Vishal Maurya
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to print all K digit
// repeating numbers
static void print_Kdigit(string S, int K)
{
// Map to store the substrings
// with their frequencies
Dictionary<string,
int> m = new Dictionary<string,
int>();
// Iterate over every substring
// and store their frequencies
// in the map
for(int i = 0; i < S.Length - K; i++)
{
string a = S.Substring(i, K);
// Increment the count of
// substrings in map
m[a] = m.GetValueOrDefault(a, 0) + 1;
}
// Iterate over all the substrings
// present in the map
foreach(KeyValuePair<string, int> x in m)
{
// Condition to check if the
// frequency of the substring
// present in the map
// is greater than 1
if (x.Value > 1)
{
Console.Write(x.Key + " - " +
x.Value + "\n");
}
}
}
// Driver code
public static void Main(string[] args)
{
// Given number in form of string
string str = "123412345123456";
// Given K
int K = 4;
// Function call
print_Kdigit(str, K);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program for the above approach
// Function to print all K digit
// repeating numbers
function print_Kdigit(S, K)
{
// Map to store the substrings
// with their frequencies
var m = new Map();
// Iterate over every substring
// and store their frequencies
// in the map
for (var i = 0; i < S.length - K;
i++) {
var a = S.substring(i,i + K);
// Increment the count of
// substrings in map
if(m.has(a))
m.set(a, m.get(a)+1)
else
m.set(a, 1)
}
// Iterate over all the substrings
// present in the map
m.forEach((value, key) => {
// Condition to check if the
// frequency of the substring
// present in the map
// is greater than 1
if (value > 1) {
document.write(key + " - " +value + "<br>")
}
});
}
// Driver Code
// Given Number in form of string
var str = "123412345123456";
// Given K
var K = 4;
// Function Call
print_Kdigit(str, K);
</script>
Producción:
1234 - 3 2345 - 2
Complejidad de tiempo: O(N*K)
Complejidad espacial: O(N) //N es la longitud de la string
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array