Given two strings a and b. Our task is to print any string which is greater than a(lexicographically) but smaller than b(lexicographically). If it is impossible to get such string, print -1;
Examples:
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
Since there can be multiple strings that may satisfy the above condition, we convert string “a” into a string that is lexicographically next to “a”.
To find lexicographically next, we start traversing the string from backward and convert all the letters “z” to letter”a”. If we encounter any letter which is not “z”, then we increment it by one and further traversal will not be carried out.If this string is not smaller than “b”, then we will print -1 as no string can satisfy the above condition.
For example, string a=”ddzzz” and string b=”deaao”.So, starting from backward, we will convert all letter “z” to letter “a” until we reach to letter “d”(in this case). Increment “d” by one (to “e”) and break out from the loop.So, string a will become “deaaa” which is lexicographically greater than “ddzzz” and smaller than “deaao”.
Implementation:
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 functionint main(){ string a = "neveropen", b = "heeks"; lexMiddle(a, b); return 0;} |
Java
// Java program to implement// above approachclass 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 Codepublic static void main(String args[]){ String a = "neveropen", 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("neveropen") 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 approachusing 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 Codepublic static void Main(){ string a = "neveropen", 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 Codelet a = "neveropen", b = "heeks";lexMiddle(a, b); // This code is contributed by avanitrachhadiya2155</script> |
Output
geekt
Time Complexity: O(n) where n is length of string ‘a’.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
