Construct the Largest Palindromic String which lies between two other Strings
Given two strings A and B of length N which contains only lowercase characters, find the lexicographically largest string C of length N which contains only lowercase characters such that the following conditions are satisfied.
- C should be lexicographically greater than the string A.
- C should be lexicographically smaller than the string B.
- C should be palindrome.
Examples:
Input: N = 3, A = “aba”, B = “ade”
Output: ada
Explanation: “ada” is lexicographically greater than the string A and lexicographically smaller than the string B and it is a palindrome.Input: N = 1, A = “z”, B = “z”
Output: -1
Approach: The idea behind the following approach is:
This problem can be solved with the some observations. Our goal is to make palindrome and it should be lexicographically larger than A but smaller than B. We will perform operations on string B. Divide B to half string and add first half to C, add a middle character (when N is odd) and again add first half to C but in reverse order. Now, to make it smaller than B and greater than A, we will change characters in C accordingly.
Below are the steps involved in the implementation of the code:
- Check A should be smaller than B otherwise return -1.
- Create a empty string ans representing C.
- Split B into two halves and add first half to ans, add a middle character (when N is odd) and again first half of B in backward direction.
- Now, to make it greater than A and smaller than B.
- Iterate in it and try changing character (on both sides) one by one through i and j variables.
- If character present at ans[i] and ans[j] is ‘a’ skip it.
- If not reduce it by one both the ans[i] and ans[j] and make the characters between i and j index of ans as ‘z’. As our goal is to make lexicographically largest.
- If ans > A and ans < B, return ans.
- Otherwise “-1”.
Below is the implementation of the code:
C++
// C++ Implementation of the code: #include <bits/stdc++.h> using namespace std; // Function to find String C string constructString( int N, string A, string B) { // If A is greater than or equal to B if (A >= B) { return "-1"; } int mid = N / 2; string ans = ""; // Form ans upto half of mid of B for ( int i = 0; i < mid; i++) ans += B[i]; string copy = ans; reverse(copy.begin(), copy.end()); if (N & 1) { ans += B[mid]; } // Making ans string palindrome ans += copy; int i = mid, j = mid; // If length of A is even if (N % 2 == 0) { i--; } while (i >= 0 && j < A.length()) { if (ans[i] == 'a' ) { i--; j++; } else { // Check whether ans is smaller // than B and greater than A if (ans < B && ans > A) { return ans; } ans[i] = ans[i] - 1; ans[j] = ans[i]; int l = i + 1; int r = j - 1; // Converting other characters to z // to form biggest lexicographically // string while (l <= r) { ans[l++] = 'z' ; ans[r--] = 'z' ; } // If ans is less than A // lexicographically if (ans > A) return ans; return "-1"; } } return "-1"; } // Driver code int main() { string A = "aaaaa"; string B = "axaae"; int N = A.length(); // Function call string res = constructString(N, A, B); cout << res << endl; return 0; } |
Java
// Java Implementation of the code: import java.util.*; public class Main { // Function to find String C public static String constructString( int N, String A, String B) { // If A is greater than or equal to B if (A.compareTo(B) >= 0 ) { return "-1" ; } int mid = N / 2 ; StringBuilder ans = new StringBuilder(); // Form ans up to half of mid of B for ( int i = 0 ; i < mid; i++) { ans.append(B.charAt(i)); } StringBuilder copy = new StringBuilder(ans); copy.reverse(); if (N % 2 == 1 ) { ans.append(B.charAt(mid)); } // Making ans string palindrome ans.append(copy); int i = mid, j = mid; // If length of A is even if (N % 2 == 0 ) { i--; } while (i >= 0 && j < A.length()) { if (ans.charAt(i) == 'a' ) { i--; j++; } else { // Check whether ans is smaller // than B and greater than A if (ans.toString().compareTo(B) < 0 && ans.toString().compareTo(A) > 0 ) { return ans.toString(); } ans.setCharAt(i, ( char )(ans.charAt(i) - 1 )); ans.setCharAt(j, ans.charAt(i)); int l = i + 1 ; int r = j - 1 ; // Converting other characters to z // to form the biggest lexicographically // string while (l <= r) { ans.setCharAt(l, 'z' ); ans.setCharAt(r, 'z' ); l++; r--; } // If ans is less than A // lexicographically if (ans.toString().compareTo(A) > 0 ) { return ans.toString(); } return "-1" ; } } return "-1" ; } // Driver code public static void main(String[] args) { String A = "aaaaa" ; String B = "axaae" ; int N = A.length(); // Function call String res = constructString(N, A, B); System.out.println(res); } } // this code is contributed by uttamdp_10 |
Python3
def constructString(N, A, B): # If A is greater than or equal to B if A > = B: return "-1" mid = N / / 2 ans = [] # Form ans up to half of mid of B for i in range (mid): ans.append(B[i]) copy = ans[:: - 1 ] if N % 2 = = 1 : ans.append(B[mid]) # Making ans string palindrome ans.extend(copy) i, j = mid, mid # If the length of A is even if N % 2 = = 0 : i - = 1 while i > = 0 and j < len (A): if ans[i] = = 'a' : i - = 1 j + = 1 else : # Check whether ans is smaller # than B and greater than A if ' '.join(ans) < B and ' '.join(ans) > A: return ''.join(ans) ans[i] = chr ( ord (ans[i]) - 1 ) ans[j] = ans[i] l, r = i + 1 , j - 1 # Converting other characters to 'z' # to form the biggest lexicographically # string while l < = r: ans[l] = 'z' ans[r] = 'z' l + = 1 r - = 1 # If ans is less than A # lexicographically if ''.join(ans) > A: return ''.join(ans) return "-1" return "-1" # Driver code A = "aaaaa" B = "axaae" N = len (A) # Function call res = constructString(N, A, B) print (res) # by phasing17 |
C#
using System; class GFG { // Function to find String C public static string ConstructString( int N, string A, string B) { // If A is greater than or equal to B if (A.CompareTo(B) >= 0) return "-1" ; int mid = N / 2; string ans = "" ; // Form ans upto half of mid of B for ( int x = 0; x < mid; x++) ans += B[x]; string copy = new string (ans.ToCharArray()); char [] charArray = copy.ToCharArray(); Array.Reverse(charArray); copy = new string (charArray); if (N % 2 == 1) ans += B[mid]; // Making ans string palindrome ans += copy; int i = mid, j = mid; // If length of A is even if (N % 2 == 0) i--; while (i >= 0 && j < A.Length) { if (ans[i] == 'a' ) { i--; j++; } else { // Check whether ans is smaller than B and greater than A if ( string .Compare(ans, B) < 0 && string .Compare(ans, A) > 0) { return ans; } ans = ans.Remove(i, 1).Insert(i, Convert.ToString(( char )(ans[i] - 1))); ans = ans.Remove(j, 1).Insert(j, Convert.ToString(ans[i])); int l = i + 1; int r = j - 1; // Converting other characters to z to form biggest lexicographically string while (l <= r) { ans = ans.Remove(l, 1).Insert(l, "z" ); ans = ans.Remove(r, 1).Insert(r, "z" ); l++; r--; } // If ans is less than A lexicographically if ( string .Compare(ans, A) > 0) return ans; return "-1" ; } } return "-1" ; } // Driver code public static void Main( string [] args) { string A = "aaaaa" ; string B = "axaae" ; int N = A.Length; // Function call string res = ConstructString(N, A, B); Console.WriteLine(res); } } |
Javascript
function constructString(N, A, B) { //If A is greater than or equal to B if (A >= B) { return "-1" ; } var mid = Math.floor(N / 2); var ans = []; //Form ans up to half of mid of B for ( var i = 0; i < mid; i++) { ans.push(B[i]); } var copy = ans.slice().reverse(); if (N % 2 === 1) { ans.push(B[mid]); } //Making ans string palindrome ans = ans.concat(copy); var i = mid; var j = mid; //If the length of A is even if (N % 2 === 0) { i -= 1; } while (i >= 0 && j < A.length) { if (ans[i] === 'a' ) { i -= 1; j += 1; } else { //Check whether ans is smaller //than B and greater than A if (ans.join( '' ) < B && ans.join( '' ) > A) { return ans.join( '' ); } ans[i] = String.fromCharCode(ans[i].charCodeAt(0) - 1); ans[j] = ans[i]; var l = i + 1; var r = j - 1; //Converting other characters to 'z' //to form the biggest lexicographically //string while (l <= r) { ans[l] = 'z' ; ans[r] = 'z' ; l += 1; r -= 1; } //If ans is less than A //lexicographically if (ans.join( '' ) > A) { return ans.join( '' ); } return "-1" ; } } return "-1" ; } //Driver code var A = "aaaaa" ; var B = "axaae" ; var N = A.length; //Function call var res = constructString(N, A, B); console.log(res); |
awzwa
Time Complexity: O(N), where N is the length of strings A and B
Auxiliary Space: O(N)