Dada una string de alfabetos ingleses en minúsculas y un número entero 0 < K <= 26. La tarea es dividir la string en dos partes (también imprimirlas) de modo que ambas partes tengan al menos k caracteres diferentes. Si hay más de una respuesta posible, escriba una que tenga la parte izquierda más pequeña. Si no hay tales respuestas, escriba «No es posible».
Ejemplos:
Entrada: str = “geeksforgeeks”, k = 4
Salida: geeks, forgeeks
La string se puede dividir en dos partes como “geeks” y “forgeeks”. Dado que “geeks” tiene cuatro caracteres diferentes ‘g’, ‘e’, ’k’ y ‘s’ y esta es la parte izquierda más pequeña, “forgeeks” también tiene al menos cuatro caracteres diferentes.
Entrada: str = “aaaabbbb”, k = 2
Salida: No es posible
Acercarse :
- La idea es contar la cantidad de caracteres distintos usando un Hashmap.
- Si el recuento de la variable distinta llega a ser igual a k , entonces se encuentra la parte izquierda de la string, así que almacene este índice, rompa el ciclo y desmarque todos los caracteres.
- Ahora ejecute un ciclo desde donde termina la string izquierda hasta el final de la string dada y repita el mismo proceso que se hizo para encontrar la string izquierda.
- Si el recuento es mayor o igual que k , entonces se podría encontrar la string correcta; de lo contrario, imprima «No es posible».
- Si es posible, imprima la string izquierda y la string derecha.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation of the above approach
#include <iostream>
#include <map>
using namespace std;
// Function to find the partition of the
// string such that both parts have at
// least k different characters
void division_of_string(string str, int k)
{
// Length of the string
int n = str.size();
// To check if the current
// character is already found
map<char, bool> has;
int ans, cnt = 0, i = 0;
// Count number of different
// characters in the left part
while (i < n) {
// If current character is not
// already found, increase cnt by 1
if (!has[str[i]]) {
cnt++;
has[str[i]] = true;
}
// If count becomes equal to k, we've
// got the first part, therefore,
// store current index and break the loop
if (cnt == k) {
ans = i;
break;
}
i++;
}
//Increment i by 1
i++;
// Clear the map
has.clear();
// Assign cnt as 0
cnt = 0;
while (i < n) {
// If the current character is not
// already found, increase cnt by 1
if (!has[str[i]]) {
cnt++;
has[str[i]] = true;
}
// If cnt becomes equal to k, the
// second part also have k different
// characters so break it
if (cnt == k) {
break;
}
i++;
}
// If the second part has less than
// k different characters, then
// print "Not Possible"
if (cnt < k) {
cout << "Not possible" << endl;
}
// Otherwise print both parts
else {
i = 0;
while (i <= ans) {
cout << str[i];
i++;
}
cout << endl;
while (i < n) {
cout << str[i];
i++;
}
cout << endl;
}
cout << endl;
}
// Driver code
int main()
{
string str = "geeksforgeeks";
int k = 4;
// Function call
division_of_string(str, k);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to find the partition of the
// string such that both parts have at
// least k different characters
static void division_of_string(char[] str, int k)
{
// Length of the string
int n = str.length;
// To check if the current
// character is already found
Map<Character, Boolean> has = new HashMap<>();
int ans = 0, cnt = 0, i = 0;
// Count number of different
// characters in the left part
while (i < n)
{
// If current character is not
// already found, increase cnt by 1
if (!has.containsKey(str[i]))
{
cnt++;
has.put(str[i], true);
}
// If count becomes equal to k, we've
// got the first part, therefore,
// store current index and break the loop
if (cnt == k)
{
ans = i;
break;
}
i++;
}
//Increment i by 1
i++;
// Clear the map
has.clear();
// Assign cnt as 0
cnt = 0;
while (i < n)
{
// If the current character is not
// already found, increase cnt by 1
if (!has.containsKey(str[i]))
{
cnt++;
has.put(str[i], true);
}
// If cnt becomes equal to k, the
// second part also have k different
// characters so break it
if (cnt == k)
{
break;
}
i++;
}
// If the second part has less than
// k different characters, then
// print "Not Possible"
if (cnt < k)
{
System.out.println("Not possible");
}
// Otherwise print both parts
else
{
i = 0;
while (i <= ans)
{
System.out.print(str[i]);
i++;
}
System.out.println("");
while (i < n)
{
System.out.print(str[i]);
i++;
}
System.out.println("");
}
System.out.println("");
}
// Driver code
public static void main(String[] args)
{
String str = "geeksforgeeks";
int k = 4;
// Function call
division_of_string(str.toCharArray(), k);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the above approach
# Function to find the partition of the
# string such that both parts have at
# least k different characters
def division_of_string(string, k) :
# Length of the string
n = len(string);
# To check if the current
# character is already found
has = {};
cnt = 0; i = 0;
# Count number of different
# characters in the left part
while (i < n) :
# If current character is not
# already found, increase cnt by 1
if string[i] not in has :
cnt += 1;
has[string[i]] = True;
# If count becomes equal to k, we've
# got the first part, therefore,
# store current index and break the loop
if (cnt == k) :
ans = i;
break;
i += 1;
# Increment i by 1
i += 1;
# Clear the map
has.clear();
# Assign cnt as 0
cnt = 0;
while (i < n) :
# If the current character is not
# already found, increase cnt by 1
if (string[i] not in has) :
cnt += 1;
has[string[i]] = True;
# If cnt becomes equal to k, the
# second part also have k different
# characters so break it
if (cnt == k) :
break;
i += 1;
# If the second part has less than
# k different characters, then
# print "Not Possible"
if (cnt < k) :
print("Not possible",end = "");
# Otherwise print both parts
else :
i = 0;
while (i <= ans) :
print(string[i],end= "");
i += 1;
print();
while (i < n) :
print(string[i],end="");
i += 1;
print()
# Driver code
if __name__ == "__main__":
string = "geeksforgeeks";
k = 4;
# Function call
division_of_string(string, k);
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the partition of the
// string such that both parts have at
// least k different characters
static void division_of_string(char[] str, int k)
{
// Length of the string
int n = str.Length;
// To check if the current
// character is already found
Dictionary<char,bool> has = new Dictionary<char,bool> ();
int ans = 0, cnt = 0, i = 0;
// Count number of different
// characters in the left part
while (i < n)
{
// If current character is not
// already found, increase cnt by 1
if (!has.ContainsKey(str[i]))
{
cnt++;
has.Add(str[i], true);
}
// If count becomes equal to k, we've
// got the first part, therefore,
// store current index and break the loop
if (cnt == k)
{
ans = i;
break;
}
i++;
}
// Increment i by 1
i++;
// Clear the map
has.Clear();
// Assign cnt as 0
cnt = 0;
while (i < n)
{
// If the current character is not
// already found, increase cnt by 1
if (!has.ContainsKey(str[i]))
{
cnt++;
has.Add(str[i], true);
}
// If cnt becomes equal to k, the
// second part also have k different
// characters so break it
if (cnt == k)
{
break;
}
i++;
}
// If the second part has less than
// k different characters, then
// print "Not Possible"
if (cnt < k)
{
Console.WriteLine("Not possible");
}
// Otherwise print both parts
else
{
i = 0;
while (i <= ans)
{
Console.Write(str[i]);
i++;
}
Console.WriteLine("");
while (i < n)
{
Console.Write(str[i]);
i++;
}
Console.WriteLine("");
}
Console.WriteLine("");
}
// Driver code
public static void Main(String[] args)
{
String str = "geeksforgeeks";
int k = 4;
// Function call
division_of_string(str.ToCharArray(), k);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
// Function to find the partition of the
// string such that both parts have at
// least k different characters
function division_of_string(str, k)
{
// Length of the string
let n = str.length;
// To check if the current
// character is already found
let has = new Map();
let ans = 0, cnt = 0, i = 0;
// Count number of different
// characters in the left part
while (i < n)
{
// If current character is not
// already found, increase cnt by 1
if (!has.has(str[i]))
{
cnt++;
has.set(str[i], true);
}
// If count becomes equal to k, we've
// got the first part, therefore,
// store current index and break the loop
if (cnt == k)
{
ans = i;
break;
}
i++;
}
//Increment i by 1
i++;
// Clear the map
has.clear();
// Assign cnt as 0
cnt = 0;
while (i < n)
{
// If the current character is not
// already found, increase cnt by 1
if (!has.has(str[i]))
{
cnt++;
has.set(str[i], true);
}
// If cnt becomes equal to k, the
// second part also have k different
// characters so break it
if (cnt == k)
{
break;
}
i++;
}
// If the second part has less than
// k different characters, then
// print "Not Possible"
if (cnt < k)
{
document.write("Not possible" + "<br/>");
}
// Otherwise print both parts
else
{
i = 0;
while (i <= ans)
{
document.write(str[i]);
i++;
}
document.write("" + "<br/>");
while (i < n)
{
document.write(str[i]);
i++;
}
document.write("" + "<br/>");
}
document.write("" + "<br/>");
}
// Driver code
let str = "geeksforgeeks";
let k = 4;
// Function call
division_of_string(str.split(''), k);
// This code is contributed by sanjoy_62.
</script>
Producción:
geeks forgeeks
Complejidad de tiempo: O(N) donde N es la longitud de la string dada.
Publicación traducida automáticamente
Artículo escrito por Vivek.Pandit y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA