Dada la string S de tamaño N que consta de K caracteres distintos y (N – K) ‘?’ s, la tarea es reemplazar todos los ‘?’ con caracteres existentes de la string, de modo que cada substring de tamaño K haya consistido únicamente en caracteres únicos. Si no es posible hacerlo, imprima “-1” .
Ejemplos:
Entrada: S = “????abcd”, K = 4
Salida: abcdabcd
Explicación:
Reemplazar los 4 ‘?’s con “abcd” modifica la string S a “abcdabcd”, lo que satisface la condición dada.Entrada: S = “?a?b?c”, K = 3
Salida: bacbac
Explicación:
Reemplazar S[0] con ‘b’, S[2] con ‘c’ y S[4] con ‘a’ modifica la string S a “bacbac”, que satisface la condición dada.
Enfoque: La idea se basa en la observación de que en la string resultante final, cada carácter debe aparecer después de exactamente K lugares, como el (K + 1) el carácter debe ser el mismo que el 1 er , (K + 2) el carácter debe ser el mismo que el 2º , y así sucesivamente.
Siga los pasos a continuación para resolver el problema:
- Inicialice un hashmap M para almacenar las posiciones de los caracteres.
- Atraviese la string S usando la variable i y si el carácter actual S[i] no es el mismo que ‘ ? ‘, luego actualice M[i % K] = S[i] .
- Recorra la string S usando la variable i y si el valor de i%k no está presente en el mapa M , imprima «-1» y salga del ciclo . De lo contrario, actualice S[i] a M[i % K] .
- Después de los pasos anteriores, si el ciclo no se rompe, imprima S como la string resultante.
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 replace all '?'
// characters in a string such
// that the given conditions are satisfied
void fillString(string s, int k)
{
unordered_map<int, char> mp;
// Traverse the string to Map the
// characters with respective positions
for (int i = 0; i < s.size(); i++) {
if (s[i] != '?') {
mp[i % k] = s[i];
}
}
// Traverse the string again and
// replace all unknown characters
for (int i = 0; i < s.size(); i++) {
// If i % k is not found in
// the Map M, then return -1
if (mp.find(i % k) == mp.end()) {
cout << -1;
return;
}
// Update S[i]
s[i] = mp[i % k];
}
// Print the string S
cout << s;
}
// Driver Code
int main()
{
string S = "????abcd";
int K = 4;
fillString(S, K);
return 0;
}
Java
// Java Program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to replace all '?'
// characters in a string such
// that the given conditions are satisfied
static void fillString(String str, int k)
{
char s[] = str.toCharArray();
HashMap<Integer, Character> mp = new HashMap<>();
// Traverse the string to Map the
// characters with respective positions
for (int i = 0; i < s.length; i++) {
if (s[i] != '?') {
mp.put(i % k, s[i]);
}
}
// Traverse the string again and
// replace all unknown characters
for (int i = 0; i < s.length; i++) {
// If i % k is not found in
// the Map M, then return -1
if (!mp.containsKey(i % k)) {
System.out.println(-1);
return;
}
// Update S[i]
s[i] = mp.getOrDefault(i % k, s[i]);
}
// Print the string S
System.out.println(new String(s));
}
// Driver Code
public static void main(String[] args)
{
String S = "????abcd";
int K = 4;
fillString(S, K);
}
}
// This code is contributed by Kingash.
Python3
# Python 3 program for the above approach
# Function to replace all '?'
# characters in a string such
# that the given conditions are satisfied
def fillString(s, k):
mp = {}
# Traverse the string to Map the
# characters with respective positions
for i in range(len(s)):
if (s[i] != '?'):
mp[i % k] = s[i]
# Traverse the string again and
# replace all unknown characters
s = list(s)
for i in range(len(s)):
# If i % k is not found in
# the Map M, then return -1
if ((i % k) not in mp):
print(-1)
return
# Update S[i]
s[i] = mp[i % k]
# Print the string S
s = ''.join(s)
print(s)
# Driver Code
if __name__ == '__main__':
S = "????abcd"
K = 4
fillString(S, K)
# This code is contributed by bgangwar59.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to replace all '?'
// characters in a string such
// that the given conditions are satisfied
static void fillString(string str, int k)
{
char[] s = str.ToCharArray();
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// Traverse the string to Map the
// characters with respective positions
for (int i = 0; i < s.Length; i++) {
if (s[i] != '?') {
mp[i % k] = s[i];
}
}
// Traverse the string again and
// replace all unknown characters
for (int i = 0; i < s.Length; i++) {
// If i % k is not found in
// the Map M, then return -1
if (!mp.ContainsKey(i % k)) {
Console.WriteLine(-1);
return;
}
// Update S[i]
s[i] = (char)mp[i % k];
}
// Print the string S
Console.WriteLine(new string(s));
}
// Driver code
static void Main()
{
string S = "????abcd";
int K = 4;
fillString(S, K);
}
}
// This code is contributed by susmitakundugoaldanga.
Javascript
<script>
// JavaScript program for the above approach
// Function to replace all '?'
// characters in a string such
// that the given conditions are satisfied
function fillString(str, k) {
var s = str.split("");
var mp = {};
// Traverse the string to Map the
// characters with respective positions
for (var i = 0; i < s.length; i++) {
if (s[i] !== "?") {
mp[i % k] = s[i];
}
}
// Traverse the string again and
// replace all unknown characters
for (var i = 0; i < s.length; i++) {
// If i % k is not found in
// the Map M, then return -1
if (!mp.hasOwnProperty(i % k)) {
document.write(-1);
return;
}
// Update S[i]
s[i] = mp[i % k];
}
// Print the string S
document.write(s.join("") + "<br>");
}
// Driver code
var S = "????abcd";
var K = 4;
fillString(S, K);
</script>
abcdabcd
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ramandeep8421 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA