Dada una string str que contiene letras en minúsculas y el carácter ‘?’ . La tarea es verificar si es posible hacer que str sea bueno o no.
Una string se llama buena si contiene una substring de longitud 26 que tiene todos los caracteres del alfabeto en minúsculas.
La tarea es verificar si es posible hacer que la string sea buena reemplazando ‘?’ caracteres con cualquier alfabeto en minúsculas. Si es posible, imprima la string modificada; de lo contrario, imprima -1 .
Ejemplos:
Entrada: str = “abcdefghijkl?nopqrstuvwxy?”
Salida: abcdefghijklmnopqrstuvwxyz
Reemplazar primero ‘?’ con ‘m’ y el segundo con ‘z’.
Entrada: str = “abcdefghijklmnopqrstuvwxyz??????”
Salida: abcdefghijklmnopqrstuvwxyzaaaaaa La
string dada ya tiene una substring que contiene los 26 alfabetos en minúsculas.
Enfoque: si la longitud de la string es inferior a 26, imprima -1 . La tarea es crear una substring de longitud 26 que tenga todos los caracteres en minúsculas. Por lo tanto, la forma más sencilla es iterar a través de todas las substrings de longitud 26 y luego, para cada substring, contar el número de ocurrencias de cada alfabeto, ignorando los signos de interrogación. Después de eso, si existe un carácter que aparece dos o más veces, esta substring no puede contener todas las letras del alfabeto y procesamos la siguiente substring. De lo contrario, podemos rellenar los signos de interrogación con las letras que no han aparecido en la substring y obtener una substring de longitud 26 que contenga todas las letras del alfabeto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns true if every
// lowercase character appears atmost once
bool valid(int cnt[])
{
// every character frequency must be not
// greater than one
for (int i = 0; i < 26; i++) {
if (cnt[i] >= 2)
return false;
}
return true;
}
// Function that returns the modified
// good string if possible
string getGoodString(string s, int n)
{
// If the length of the string is less than n
if (n < 26)
return "-1";
// Sub-strings of length 26
for (int i = 25; i < n; i++) {
// To store frequency of each character
int cnt[26] = { 0 };
// Get the frequency of each character
// in the current sub-string
for (int j = i; j >= i - 25; j--) {
cnt[s[j] - 'a']++;
}
// Check if we can get sub-string containing all
// the 26 characters
if (valid(cnt)) {
// Find which character is missing
int cur = 0;
while (cnt[cur] > 0)
cur++;
for (int j = i - 25; j <= i; j++) {
// Fill with missing characters
if (s[j] == '?') {
s[j] = cur + 'a';
cur++;
// Find the next missing character
while (cnt[cur] > 0)
cur++;
}
}
// Return the modified good string
return s;
}
}
return "-1";
}
// Driver code
int main()
{
string s = "abcdefghijkl?nopqrstuvwxy?";
int n = s.length();
cout << getGoodString(s, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function that returns true if every
// lowercase character appears atmost once
static boolean valid(int []cnt)
{
// every character frequency must be not
// greater than one
for (int i = 0; i < 26; i++)
{
if (cnt[i] >= 2)
return false;
}
return true;
}
// Function that returns the modified
// good string if possible
static String getGoodString(String ss, int n)
{
char[] s=ss.toCharArray();
// If the length of the string is less than n
if (n < 26)
return "-1";
// To store frequency of each character
int[] cnt = new int[27];
// Sub-strings of length 26
for (int i = 25; i < n; i++)
{
// Get the frequency of each character
// in the current sub-string
for (int j = i; j >= i - 25; j--)
{
if (s[j] != '?')
cnt[((int)s[j] - (int)'a')]++;
}
// Check if we can get sub-string containing all
// the 26 characters
if (valid(cnt))
{
// Find which character is missing
int cur = 0;
while (cnt[cur] > 0)
cur++;
for (int j = i - 25; j <= i; j++)
{
// Fill with missing characters
if (s[j] == '?')
{
s[j] = (char)(cur + (int)('a'));
cur++;
// Find the next missing character
while (cnt[cur] > 0)
cur++;
}
}
// Return the modified good string
return new String(s);
}
}
return "-1";
}
// Driver code
public static void main (String[] args)
{
String s = "abcdefghijkl?nopqrstuvwxy?";
int n = s.length();
System.out.println(getGoodString(s, n));
}
}
// This code is contributed by chandan_jnu
Python3
# Python3 implementation of the approach
# Function that returns true if every
# lowercase character appears atmost once
def valid(cnt):
# Every character frequency must
# be not greater than one
for i in range(0, 26):
if cnt[i] >= 2:
return False
return True
# Function that returns the modified
# good string if possible
def getGoodString(s, n):
# If the length of the string is
# less than n
if n < 26:
return "-1"
# Sub-strings of length 26
for i in range(25, n):
# To store frequency of each character
cnt = [0] * 26
# Get the frequency of each character
# in the current sub-string
for j in range(i, i - 26, -1):
if s[j] != '?':
cnt[ord(s[j]) - ord('a')] += 1
# Check if we can get sub-string
# containing the 26 characters all
if valid(cnt):
# Find which character is missing
cur = 0
while cur < 26 and cnt[cur] > 0:
cur += 1
for j in range(i - 25, i + 1):
# Fill with missing characters
if s[j] == '?':
s[j] = chr(cur + ord('a'))
cur += 1
# Find the next missing character
while cur < 26 and cnt[cur] > 0:
cur += 1
# Return the modified good string
return ''.join(s)
return "-1"
# Driver code
if __name__ == "__main__":
s = "abcdefghijkl?nopqrstuvwxy?"
n = len(s)
print(getGoodString(list(s), n))
# This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
class GFG
{
// Function that returns true if every
// lowercase character appears atmost once
static bool valid(int []cnt)
{
// every character frequency must be not
// greater than one
for (int i = 0; i < 26; i++)
{
if (cnt[i] >= 2)
return false;
}
return true;
}
// Function that returns the modified
// good string if possible
static string getGoodString(string ss, int n)
{
char[] s = ss.ToCharArray();
// If the length of the string is less than n
if (n < 26)
return "-1";
// To store frequency of each character
int[] cnt = new int[27];
// Sub-strings of length 26
for (int i = 25; i < n; i++)
{
// Get the frequency of each character
// in the current sub-string
for (int j = i; j >= i - 25; j--)
{
if (s[j] != '?')
cnt[((int)s[j] - (int)'a')]++;
}
// Check if we can get sub-string containing all
// the 26 characters
if (valid(cnt))
{
// Find which character is missing
int cur = 0;
while (cnt[cur] > 0)
cur++;
for (int j = i - 25; j <= i; j++)
{
// Fill with missing characters
if (s[j] == '?')
{
s[j] = (char)(cur + (int)('a'));
cur++;
// Find the next missing character
while (cnt[cur] > 0)
cur++;
}
}
// Return the modified good string
return new String(s);
}
}
return "-1";
}
// Driver code
static void Main()
{
string s = "abcdefghijkl?nopqrstuvwxy?";
int n = s.Length;
Console.WriteLine(getGoodString(s, n));
}
}
// This code is contributed by chandan_jnu
PHP
<?php
// PHP implementation of the approach
// Function that returns true if every
// lowercase character appears atmost once
function valid(&$cnt)
{
// every character frequency must
// be not greater than one
for ($i = 0; $i < 26; $i++)
{
if ($cnt[$i] >= 2)
return false;
}
return true;
}
// Function that returns the modified
// good string if possible
function getGoodString($s, $n)
{
// If the length of the string is
// less than n
if ($n < 26)
return "-1";
// Sub-strings of length 26
for ($i = 25; $i < $n; $i++)
{
// To store frequency of each character
$cnt = array_fill(0, 26, NULL);
// Get the frequency of each character
// in the current sub-string
for ($j = $i; $j >= $i - 25; $j--)
{
if ($s[$j] != '?')
$cnt[ord($s[$j]) - ord('a')]++;
}
// Check if we can get sub-string
// containing all the 26 characters
if (valid($cnt))
{
// Find which character is missing
$cur = 0;
while ($cur < 26 && $cnt[$cur] > 0)
$cur++;
for ($j = $i - 25; $j <= $i; $j++)
{
// Fill with missing characters
if ($s[$j] == '?')
{
$s[$j] = chr($cur + ord('a'));
$cur++;
// Find the next missing character
while ($cur < 26 && $cnt[$cur] > 0)
$cur++;
}
}
// Return the modified good string
return $s;
}
}
return "-1";
}
// Driver code
$s = "abcdefghijkl?nopqrstuvwxy?";
$n = strlen($s);
echo getGoodString($s, $n);
// This code is contributed by ita_c
?>
Javascript
<script>
// JavaScript implementation of the approach
// Function that returns true if every
// lowercase character appears atmost once
function valid(cnt) {
// every character frequency must be not
// greater than one
for (var i = 0; i < 26; i++) {
if (cnt[i] >= 2) return false;
}
return true;
}
// Function that returns the modified
// good string if possible
function getGoodString(ss, n) {
var s = ss.split("");
// If the length of the string is less than n
if (n < 26) return "-1";
// Sub-strings of length 26
for (var i = 25; i < n; i++) {
// To store frequency of each character
var cnt = new Array(26).fill(0);
// Get the frequency of each character
// in the current sub-string
for (var j = i; j >= i - 25; j--) {
cnt[s[j].charCodeAt(0) - "a".charCodeAt(0)]++;
}
// Check if we can get sub-string containing all
// the 26 characters
if (valid(cnt)) {
// Find which character is missing
var cur = 0;
while (cnt[cur] > 0) cur++;
for (var j = i - 25; j <= i; j++) {
// Fill with missing characters
if (s[j] === "?") {
s[j] = String.fromCharCode(cur + "a".charCodeAt(0));
cur++;
// Find the next missing character
while (cnt[cur] > 0) cur++;
}
}
// Return the modified good string
return s.join("");
}
}
return "-1";
}
// Driver code
var s = "abcdefghijkl?nopqrstuvwxy?";
var n = s.length;
document.write(getGoodString(s, n));
</script>
Producción:
abcdefghijklmnopqrstuvwxyz
Complejidad de tiempo: O(N 2 ), donde N es el tamaño de la string dada.
Espacio Auxiliar: O(26)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA