Dadas dos strings a y b . Nuestra tarea es imprimir cualquier string que sea mayor que a (lexicográficamente) pero menor que b (lexicográficamente). Si es imposible obtener dicha string, imprima -1;
Ejemplos:
Input : a = "abg", b = "abj" Output : abh The string "abh" is lexicographically greater than "abg" and smaller than "abj" Input : a = "abc", b = "abd" Output :-1 There is no string which is lexicographically greater than a but smaller than b/
Dado que puede haber múltiples strings que pueden satisfacer la condición anterior, convertimos la string «a» en una string que está lexicográficamente al lado de «a».
Para buscar lexicográficamente a continuación, comenzamos a recorrer la string desde atrás y convertimos todas las letras «z» en letras «a». Si encontramos alguna letra que no sea «z», la incrementamos en uno y no se realizará más recorrido. Si esta string no es más pequeña que «b», imprimiremos -1 ya que ninguna string puede satisfacer la condición anterior.
Por ejemplo, string a=”ddzzz” y string b=”deaao”. Entonces, comenzando desde atrás, convertiremos todas las letras “z” en letras “a” hasta llegar a la letra “d” (en este caso). Incremente «d» en uno (a «e») y salga del bucle. Entonces, la string a se convertirá en «deaaa», que es lexicográficamente mayor que «ddzzz» y menor que «deaao».
C++
// C++ program to implement above approach
#include <iostream>
using namespace std;
// function to find lexicographically mid
// string.
void lexMiddle(string a, string b)
{
// converting string "a" into its
// lexicographically next string
for (int i = a.length() - 1; i >= 0; i--) {
// converting all letter "z" to letter "a"
if (a[i] == 'z')
a[i] = 'a';
else {
// if letter other than "z" is
// encountered, increment it by one
// and break
a[i]++;
break;
}
}
// if this new string "a" is lexicographically
// smaller than b
if (a < b)
cout << a;
else
cout << -1;
}
// Driver function
int main()
{
string a = "geeks", b = "heeks";
lexMiddle(a, b);
return 0;
}
Java
// Java program to implement
// above approach
class GFG
{
// function to find lexicographically
// mid String.
static void lexMiddle(String a, String b)
{
String new_String = "";
// converting String "a" into its
// lexicographically next String
for (int i = a.length() - 1; i >= 0; i--)
{
// converting all letter
// "z" to letter "a"
if (a.charAt(i) == 'z')
new_String = 'a' + new_String;
else
{
// if letter other than "z" is
// encountered, increment it by
// one and break
new_String = (char)(a.charAt(i) + 1) +
new_String;
//compose the remaining string
for(int j = i - 1; j >= 0; j--)
new_String = a.charAt(j) + new_String;
break;
}
}
// if this new String new_String is
// lexicographically smaller than b
if (new_String.compareTo(b) < 0)
System.out.println(new_String);
else
System.out.println(-1);
}
// Driver Code
public static void main(String args[])
{
String a = "geeks", b = "heeks";
lexMiddle(a, b);
}
}
// This code is contributed
// by Arnab Kundu
Python3
# Python3 program to implement above approach
# function to find lexicographically mid
# string.
def lexMiddle( a, b):
# converting string "a" into its
# lexicographically next string
for i in range(len(a)-1,-1,-1):
ans=[]
# converting all letter "z" to letter "a"
if (a[i] == 'z'):
a[i] = 'a'
else:
# if letter other than "z" is
# encountered, increment it by one
# and break
a[i]=chr(ord(a[i])+1)
break
# if this new string "a" is lexicographically
# smaller than b
if (a < b):
return a
else:
return -1
# Driver function
if __name__=='__main__':
a = list("geeks")
b = list("heeks")
ans=lexMiddle(a, b)
ans = ''.join(map(str, ans))
print(ans)
# this code is contributed by ash264
C#
// C# program to implement above approach
using System;
class GFG
{
// function to find lexicographically
// mid String.
static void lexMiddle(string a, string b)
{
string new_String = "";
// converting String "a" into its
// lexicographically next String
for (int i = a.Length - 1; i >= 0; i--)
{
// converting all letter
// "z" to letter "a"
if (a[i] == 'z')
new_String = 'a' + new_String;
else
{
// if letter other than "z" is
// encountered, increment it by
// one and break
new_String = (char)(a[i] + 1) +
new_String;
//compose the remaining string
for(int j = i - 1; j >= 0; j--)
new_String = a[j] + new_String;
break;
}
}
// if this new String new_String is
// lexicographically smaller than b
if (new_String.CompareTo(b) < 0)
Console.Write(new_String);
else
Console.Write(-1);
}
// Driver Code
public static void Main()
{
string a = "geeks", b = "heeks";
lexMiddle(a, b);
}
}
// This code is contributed by ita_c
Javascript
<script>
// Javascript program to implement
// above approach
// Function to find lexicographically
// mid String.
function lexMiddle(a, b)
{
let new_String = "";
// Converting String "a" into its
// lexicographically next String
for(let i = a.length - 1; i >= 0; i--)
{
// Converting all letter
// "z" to letter "a"
if (a[i] == 'z')
new_String = 'a' + new_String;
else
{
// If letter other than "z" is
// encountered, increment it by
// one and break
new_String = String.fromCharCode(
a[i].charCodeAt(0) + 1) + new_String;
// Compose the remaining string
for(let j = i - 1; j >= 0; j--)
new_String = a[j] + new_String;
break;
}
}
// If this new String new_String is
// lexicographically smaller than b
if (new_String < (b))
document.write(new_String);
else
document.write(-1);
}
// Driver Code
let a = "geeks", b = "heeks";
lexMiddle(a, b);
// This code is contributed by avanitrachhadiya2155
</script>
geekt
Complejidad de tiempo: O(n) donde n es la longitud de la string ‘a’