Horje
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);

Output

awzwa

Time Complexity: O(N), where N is the length of strings A and B
Auxiliary Space: O(N)


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Difference between Recursion and Dynamic Programming Difference between Recursion and Dynamic Programming
How to get started with DSA for BackEnd Developer Interview? How to get started with DSA for BackEnd Developer Interview?
Odd level sum of given Binary Tree Odd level sum of given Binary Tree
Find the tasks completed by soldiers based on their ranks Find the tasks completed by soldiers based on their ranks
Implementing Regular Expression Matching Implementing Regular Expression Matching

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 11



 

Horje