La string lexicográficamente más pequeña con el período K posible reemplazando ‘?’ de una string dada

Dada una string S que consta de N caracteres en minúsculas y el carácter ‘?’ y un entero positivo K , la tarea es reemplazar cada carácter ‘?’ con algunos alfabetos en minúsculas de modo que la string dada se convierte en un punto de K . Si no es posible hacerlo, imprima “-1” .

Se dice que una string es un período de K si y solo si la longitud de la string es un múltiplo de K y para todos los valores posibles de i sobre el rango [0, K) el valor S[i + K], S[ i + 2*K], S[i + 3*K], …, permanece igual.

Ejemplos:

Entrada: S = “ab??”, K = 2
Salida: abab

Entrada: S = “??????”, K = 3
Salida: aaaaaa

Enfoque ingenuo: el enfoque dado también se puede resolver generando todas las combinaciones posibles de strings reemplazando cada carácter ‘?’ con cualquier carácter en minúscula e imprima esa string que tiene cada substring de tamaño K es la misma.

Complejidad de tiempo: O(26 ^M ), donde M es el número de ‘?’ en la string S.
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior también se puede optimizar recorriendo la string de tal manera que se atraviesen los caracteres primero, segundo, tercero, etc. y si todos los caracteres son ‘?’ luego reemplácelo con el carácter ‘a’ . De lo contrario, si solo existe un carácter distinto en cada posición respectiva, reemplace ‘?’ con ese carácter, de lo contrario, la string no se puede modificar según los criterios dados y, por lo tanto, imprimir «-1». Siga los pasos a continuación para resolver el problema:

• Iterar un ciclo sobre el rango [0, K] usando la variable i y realizar los siguientes pasos:
  • Inicialice un mapa , diga M para almacenar la frecuencia de los caracteres de la substring en las posiciones i .
  • Recorre la string dada sobre el rango [i, N] usando la variable j con un incremento de K y almacena la frecuencia del carácter S[j] por 1 en el mapa M .
  • Después de completar los pasos anteriores, realice lo siguiente:
    • Si el tamaño del mapa es mayor que 2 , imprima «-1» y salga del bucle .
    • De lo contrario, si el tamaño del mapa es 2 , reemplace cada ‘?’ con ese carácter diferente.
    • De lo contrario, reemplace todos los ‘?’ con el carácter ‘a’ .
• Después de completar los pasos anteriores, si la string se puede modificar, imprima la string S como la string de resultado.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include "bits/stdc++.h"
using namespace std;
 
// Function to modify the given string
// such that string S is a period of K
string modifyString(string& S, int K)
{
 
    int N = S.length();
 
    // Iterate over the range [0, K]
    for (int i = 0; i < K; i++) {
 
        // Stores the frequency of the
        // characters S[i + j*K]
        map<char, int> M;
 
        // Iterate over the string with
        // increment of K
        for (int j = i; j < N; j += K) {
            M[S[j]]++;
        }
 
        // Print "-1"
        if (M.size() > 2) {
            return "-1";
        }
        else if (M.size() == 1) {
            if (M['?'] != 0) {
 
                // Replace all characters
                // of the string with '?'
                // to 'a' to make it smallest
                for (int j = i; j < N; j += K) {
                    S[j] = 'a';
                }
            }
        }
 
        // Otherwise
        else if (M.size() == 2) {
            char ch;
 
            // Find the character other
            // than '?'
            for (auto& it : M) {
                if (it.first != '?') {
                    ch = it.first;
                }
            }
 
            // Replace all characters
            // of the string with '?'
            // to character ch
            for (int j = i; j < N; j += K) {
                S[j] = ch;
            }
        }
 
        // Clear the map M
        M.clear();
    }
 
    // Return the modified string
    return S;
}
 
// Driver Code
int main()
{
 
    string S = "ab??";
    int K = 2;
    cout << modifyString(S, K);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
  // Function to modify the given String
  // such that String S is a period of K
  static String modifyString(char[] S, int K)
  {
 
    int N = S.length;
 
    // Iterate over the range [0, K]
    for (int i = 0; i < K; i++) {
 
      // Stores the frequency of the
      // characters S[i + j*K]
      HashMap<Character,Integer> M = new HashMap<>();
 
      // Iterate over the String with
      // increment of K
      for (int j = i; j < N; j += K) {
 
        if(M.containsKey(S[j])){
          M.put(S[j], M.get(S[j])+1);
        }
        else{
          M.put(S[j], 1);
        }
      }
 
      // Print "-1"
      if (M.size() > 2) {
        return "-1";
      }
      else if (M.size() == 1) {
        if (M.get('?') != 0) {
 
          // Replace all characters
          // of the String with '?'
          // to 'a' to make it smallest
          for (int j = i; j < N; j += K) {
            S[j] = 'a';
          }
        }
      }
 
      // Otherwise
      else if (M.size() == 2) {
        char ch=' ';
 
        // Find the character other
        // than '?'
        for (Map.Entry<Character,Integer> entry : M.entrySet()) {
          if (entry.getKey() != '?') {
            ch = entry.getKey();
          }
        }
 
        // Replace all characters
        // of the String with '?'
        // to character ch
        for (int j = i; j < N; j += K) {
          S[j] = ch;
        }
      }
 
      // Clear the map M
      M.clear();
    }
 
    // Return the modified String
    return String.valueOf(S);
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    String S = "ab??";
    int K = 2;
    System.out.print(modifyString(S.toCharArray(), K));
  }
}
 
// This code is contributed by umadevi9616

# python 3 program for the above approach
 
# Function to modify the given string
# such that string S is a period of K
def modifyString(S,K):
    N = len(S)
    S = list(S)
 
    # Iterate over the range [0, K]
    for i in range(K):
        # Stores the frequency of the
        # characters S[i + j*K]
        M = {}
 
        # Iterate over the string with
        # increment of K
        for j in range(i,N,K):
            if S[j] in M:
                M[S[j]] += 1
            else:
                M[S[j]] = 1
 
        # Print "-1"
        if (len(M) > 2):
            return "-1"
 
        elif (len(M) == 1):
            if (M['?'] != 0):
 
                # Replace all characters
                # of the string with '?'
                # to 'a' to make it smallest
                for j in range(i,N,K):
                    S[j] = 'a'
 
        # Otherwise
        elif(len(M) == 2):
            ch = ''
 
            # Find the character other
            # than '?'
            for key,value in M.items():
                if (key != '?'):
                    ch = key
            # Replace all characters
            # of the string with '?'
            # to character ch
            for j in range(i,N,K):
                S[j] = ch
 
        # Clear the map M
        M.clear()
    S = ''.join(S)
 
    # Return the modified string
    return S
 
# Driver Code
if __name__ == '__main__':
    S = "ab??"
    K = 2
    print(modifyString(S, K))
     
    # This code is contributed by ipg2016107.

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG {
 
  // Function to modify the given String
  // such that String S is a period of K
  static String modifyString(char[] S, int K) {
 
    int N = S.Length;
 
    // Iterate over the range [0, K]
    for (int i = 0; i < K; i++) {
 
      // Stores the frequency of the
      // characters S[i + j*K]
      Dictionary<char, int> M = new Dictionary<char, int>();
 
      // Iterate over the String with
      // increment of K
      for (int j = i; j < N; j += K) {
 
        if (M.ContainsKey(S[j])) {
          M.Add(S[j], M[S[j]] + 1);
        } else {
          M.Add(S[j], 1);
        }
      }
 
      // Print "-1"
      if (M.Count > 2) {
        return "-1";
      } else if (M.Count == 1) {
        if (M['?'] != 0) {
 
          // Replace all characters
          // of the String with '?'
          // to 'a' to make it smallest
          for (int j = i; j < N; j += K) {
            S[j] = 'a';
          }
        }
      }
 
      // Otherwise
      else if (M.Count == 2) {
        char ch = ' ';
 
        // Find the character other
        // than '?'
        foreach (KeyValuePair<char, int> entry in M) {
          if (entry.Key != '?') {
            ch = entry.Key;
          }
        }
 
        // Replace all characters
        // of the String with '?'
        // to character ch
        for (int j = i; j < N; j += K) {
          S[j] = ch;
        }
      }
 
      // Clear the map M
      M.Clear();
    }
 
    // Return the modified String
    return String.Join("",S);
  }
 
  // Driver Code
  public static void Main(String[] args) {
 
    String S = "ab??";
    int K = 2;
    Console.Write(modifyString(S.ToCharArray(), K));
  }
}
 
// This code is contributed by umadevi9616

<script>
 
// JavaScript program for the above approach
 
// Function to modify the given string
// such that string S is a period of K
function modifyString(S, K)
{
    let N = S.length;
 
    // Iterate over the range [0, K]
    for(let i = 0; i < K; i++)
    {
         
        // Stores the frequency of the
        // characters S[i + j*K]
        let M = new Map();
 
        // Iterate over the string with
        // increment of K
        for(let j = i; j < N; j += K)
        {
            if (M.has(S[j]))
            {
                M.set(M.get(S[j]),
                      M.get(S[j]) + 1);
            }
            else
            {
                M.set(S[j], 1);
            }
        }
 
        // Print "-1"
        if (M.size > 2)
        {
            return "-1";
        }
        else if (M.size == 1)
        {
            if (M.has('?'))
            {
                 
                // Replace all characters
                // of the string with '?'
                // to 'a' to make it smallest
                for(let j = i; j < N; j += K)
                {
                    S = S.replace(S[j], 'a');
                }
            }
        }
 
        // Otherwise
        else if (M.size == 2)
        {
            let ch;
 
            // Find the character other
            // than '?'
            for(let it of M.keys())
            {
                if (it != '?')
                {
                    ch = it;
                }
            }
 
            // Replace all characters
            // of the string with '?'
            // to character ch
            for(let j = i; j < N; j += K)
            {
                S = S.replace(S[j], ch);
            }
        }
         
        // Clear the map M
        M.clear();
    }
 
    // Return the modified string
    return S;
}
 
// Driver Code
let S = "ab??";
let K = 2;
 
document.write(modifyString(S, K));
 
// This code is contributed by Potta Lokesh
 
</script>

abab

Complejidad temporal: O(N)
Espacio auxiliar: O(1)