Dada una string S que contiene una letra y un dígito y un número entero K donde, 
y 
. La tarea es devolver la K-ésima letra de la nueva string S’ .
La nueva string S’ se forma a partir de la antigua string S mediante los siguientes pasos:
1. Si el carácter que se lee es una letra , esa letra se agrega al final de S’ .
2. Si el carácter leído es un dígito , entonces la string completa S’ se escribe repetidamente d-1 veces más en total.
Nota: Se garantiza que la nueva string tendrá menos de2^63 letras.
Ejemplos:
Entrada: S = “geeks2for2”, K = 15
Salida: “e”
Explicación: La nueva string S’ = “geeksgeeksforgeeksgeeksfor”. La letra 15 es «e».
Entrada: S = “a2345”, K = 100
Salida: “a”
Explicación: La nueva string S’=”a” se repite 120 veces. La letra número 100 es «a».
Tomemos una nueva string como S’ = “geeksgeeksgeeksgeeksgeeks” y un índice K = 22 , luego la respuesta en K = 22 es la misma si K = 2 .
En general, cuando una string es igual a alguna palabra con tamaño de longitud repetida varias veces (como geeks con tamaño = 5 repetido 5 veces), entonces la respuesta será la misma para el índice K que para el índice K % tamaño _
Usando esta idea y trabajando hacia atrás , hacemos un seguimiento del tamaño de la nueva string S’ . Siempre que la string S’ sea igual a alguna palabra repetida dveces, podemos reducir K a K % (longitud de (palabra)) .
Primero encontramos la longitud de la nueva string S’ . Después, trabajaremos hacia atrás , haciendo un seguimiento del tamaño: la longitud de la nueva string después de analizar los símbolos S[0], S[1], …, S[i] .
Si vemos un dígito S[i] , significa que el tamaño de la nueva string después de analizar S[0], S[1], …, S[i-1] será (tamaño / toInteger(S[i]) ) . De lo contrario, será de tamaño – 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the K-th letter from new String.
string K_thletter(string S, int K)
{
int N = S.size();
long size = 0;
// finding size = length of new string S'
for (int i = 0; i < N; ++i) {
if (isdigit(S[i]))
size = size * (S[i] - '0');
else
size += 1;
}
// get the K-th letter
for (int i = N - 1; i >= 0; --i) {
K %= size;
if (K == 0 && isalpha(S[i]))
return (string) "" + S[i];
if (isdigit(S[i]))
size = size / (S[i] - '0');
else
size -= 1;
}
}
// Driver program
int main()
{
string S = "geeks2for2";
int K = 15;
cout << K_thletter(S, K);
return 0;
}
// This code is written by Sanjit_Prasad
Java
// Java implementation of above approach
class GFG
{
// Function to return the K-th letter from new String.
static String K_thletter(String S, int K)
{
int N = S.length();
long size = 0;
// finding size = length of new string S'
for (int i = 0; i < N; ++i)
{
if (Character.isDigit(S.charAt(i)))
{
size = size * (S.charAt(i) - '0');
}
else
{
size += 1;
}
}
// get the K-th letter
for (int i = N - 1; i >= 0; --i)
{
K %= size;
if (K == 0 && Character.isAlphabetic(S.charAt(i)))
{
return (String) "" + S.charAt(i);
}
if (Character.isDigit(S.charAt(i)))
{
size = size / (S.charAt(i) - '0');
}
else
{
size -= 1;
}
}
return null;
}
// Driver program
public static void main(String[] args)
{
String S = "geeks2for2";
int K = 15;
System.out.println(K_thletter(S, K));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of above approach # Function to return the K-th letter # from new String. def K_thletter(S, K): N = len(S) size = 0 # finding size = length of new string S' for i in range(0, N): if S[i].isdigit(): size = size * int(S[i]) else: size += 1 # get the K-th letter for i in range(N - 1, -1, -1): K %= size if K == 0 and S[i].isalpha(): return S[i] if S[i].isdigit(): size = size // int(S[i]) else: size -= 1 # Driver Code if __name__ == "__main__": S = "geeks2for2" K = 15 print(K_thletter(S, K)) # This code is contributed # by Rituraj Jain
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to return the K-th letter from new String.
static String K_thletter(String S, int K)
{
int N = S.Length;
long size = 0;
// finding size = length of new string S'
for (int i = 0; i < N; ++i)
{
if (char.IsDigit(S[i]))
{
size = size * (S[i] - '0');
}
else
{
size += 1;
}
}
// get the K-th letter
for (int i = N - 1; i >= 0; --i)
{
K %= (int)size;
if (K == 0 && char.IsLetter(S[i]))
{
return (String) "" + S[i];
}
if (char.IsDigit(S[i]))
{
size = size / (S[i] - '0');
}
else
{
size -= 1;
}
}
return null;
}
// Driver code
public static void Main(String[] args)
{
String S = "geeks2for2";
int K = 15;
Console.WriteLine(K_thletter(S, K));
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of above approach
function isAlphaNumeric(str) {
var code, i, len;
for (i = 0, len = str.length; i < len; i++) {
code = str.charCodeAt(i);
if (!(code > 47 && code < 58) && // numeric (0-9)
!(code > 64 && code < 91) && // upper alpha (A-Z)
!(code > 96 && code < 123)) { // lower alpha (a-z)
return false;
}
}
return true;
};
// Function to return the K-th letter from new String.
function K_thletter(S, K)
{
var N = S.length;
var size = 0;
// finding size = length of new string S'
for (var i = 0; i < N; ++i) {
if (Number.isInteger(parseInt(S[i])))
size = size * (S[i].charCodeAt(0) - '0'.charCodeAt(0));
else
size += 1;
}
// get the K-th letter
for (var i = N - 1; i >= 0; --i) {
K %= size;
if (K == 0 && isAlphaNumeric(S[i]))
return "" + S[i];
if (Number.isInteger(parseInt(S[i])))
size = size / (S[i].charCodeAt(0) - '0'.charCodeAt(0));
else
size -= 1;
}
}
// Driver program
var S = "geeks2for2";
var K = 15;
document.write( K_thletter(S, K));
// This code is contributed by imporrtantly.
</script>
Producción:
e
Complejidad temporal: O(N), donde N es la longitud de S.
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA