Convert given string to Palindrome with given substring

Question

Given a String S1 and String S2. Convert string S1 to a palindrome string such S2 is a substring of that palindromic string. Only operation allowed on S1 is replacement of any character with any other character. Find minimum number of operations required.

I have written this code, it works okay to count how many changes need to be done with regural string to make in to palindrome, but I do not know how to make it work lets say with input as string n = "aaaaa" and string (substring) m = "bbb" and the output has to be 3, because three changes are needed to make string abbba in this case

This is my code

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    string n = "aaaaa";
    string m = "bbb";

    if (n.size() <= m.size())
    {
        cnt = -1
    }

    if (n.size() > m.size())
    {
        string x, y;

       int cnt=0;

       if(n.size()%2!=0)
          {
                x=n.substr(0,n.size()/2);
                y=n.substr(n.size()/2+1);
               reverse(y.begin(),y.end());
          }
            else if(n.size()%2==0)
            {
                x=n.substr(0,n.size()/2);
                y=n.substr(n.size()/2);
                reverse(y.begin(),y.end());
            }
                for(int i=0;i<n.size();i++)
                    if(x[i]!=y[i])
                    cnt++;
              cout<<cnt<<endl;
    }

  }

Answer 1

Logic is to place s2 at every position in s1 and calculate cost for the same. Output the minimum cost among them. The algorithm has a time complexity of O(n^2).

#include<bits/stdc++.h>
using namespace std;

int main(){

    string s1,s2;
    cin>>s1>>s2;
    int l1=s1.length(),l2=s2.length();
    int ans=INT_MAX;
    if(l2>l1){

        cout<<-1<<endl; // not possible
        return 0;
    }
    for(int i=0 ; i<l1-l2+1 ; i++){

        string temp=s1.substr(0,i)+s2+s1.substr(i+l2); // place s2 in all possible positions in s1
        int cost=0;
        // calculate cost to place s2
        for(int j=i ; j<i+l2 ; j++){

            if(s1[j]!=temp[j])
                cost++;
        }
        int z=0;
        // find the cost to convert new string to palindrome
        for(int j=0 ; j<ceil(l1/2.0) ; j++){

            if((j<i || j>=i+l2) && temp[j]!=temp[l1-j-1]) // if s2 is in the first half of new string
                cost++;
            else if(temp[j]!=temp[l1-j-1] && (l1-j-1<i || l1-j-1>=i+l2)) // if s2 is in the second half of new string
                cost++;
            else if(temp[j]!=temp[l1-j-1]){ // if s2 is in both halves

                z=1;
                break;
            }
        }
        if(z==0)
            ans=min(ans,cost);
    }
    if(ans==INT_MAX)
        cout<<-1<<endl;
    else
        cout<<ans<<endl;
    return 0;
}

Answer 2

I got this question for an online coding interview at a FANG company in December last year. Couldn't solve it at the time but I revisited it and this is the solution I came up with. I've tested the code but feel free to test it out yourself and rectify and comment below if you find any bugs.

import java.util.Scanner;

public class PalindromeSubstring{

    public static int getCost(String s, String sPal){
        /*
        returns Cost i.e. no. of character replacement operations in s required to transform s to sPal
         */

        int cost = 0;

        for(int i=0; i<s.length(); i++)
            if(s.charAt(i) != sPal.charAt(i))
                cost += 1;

        return cost;
    }

    public static String buildPalindrome(String s, boolean part){
        /*
        Takes string s and boolean, part, to indicate which part of s is to be retained while constructing palindrome
        If part is true then left-half of s is retained and if false, then right-half is retained.
        Eg.:  s: london, part: true => output: lonnol
              s: paris, part: false => output: siris
         */

        String halfString;

        // retain left part of s
        if(part){
            halfString = s.substring(0, s.length()/2);
            if(isEvenString(s))
                return halfString.concat(new StringBuilder(halfString).reverse().toString());
            else
                return halfString.concat(new StringBuilder(s.substring(0, s.length()/2+1)).reverse().toString());
        }

        // retain right part s
        else {
            halfString = s.substring(s.length()/2);
            if (isEvenString(s)) {
                return new StringBuilder(halfString).reverse().toString().concat(halfString);
            } else {
                return new StringBuilder(halfString).reverse().toString().concat(halfString.substring(1));
            }
        }
    }

    public static boolean isEvenString(String s){
        return s.length()%2==0;
    }

    public static boolean containsEqualChars(String s){
        /*
        If all characters in String s are equal then return true
         */

        char c = s.charAt(0);
        for(int i=1; i<s.length(); i++){
            if(s.charAt(i) != c)
                return false;
        }
        return true;
    }

    public static String getPalindromicSubstring(String s1, String s2){

        String palindromicSubstring, s1Pal, s2Rev = new StringBuilder(s2).reverse().toString();
        int i=0, cost, minCost=5001, minCostPos = -1;

        /*
        if substring length is greater than original string or
        if substring is not a palindrome and substring length is greater than half-length of original string then
        output not possible, handled separately for both even and odd cases
         */
        if (s1.length() < s2.length() || (!s2.equals(s2Rev) && s2.length()>s1.length()/2 && isEvenString(s1)) ||
                (!s2.equals(s2Rev) && s2.length()>s1.length()/2+1 && !isEvenString(s1)))
            return "";

        // if substring is a palindrome and s1 does not contain s2
        if(s2.equals(s2Rev) && !s1.contains(s2)){

            /*
            if s2 is a substring of just one repeated character eg.: bbb, therefore s2 is a palindrome and if
            s1 and s2 are either even or odd or vice-versa respectively then increment s2 by one more character and
            eventually place s2 in s1 (s2 retains its original substring form and is placed in s1 with minimum
            replacement operations)
             */
            if(containsEqualChars(s2) &&
                    ((isEvenString(s1) && !isEvenString(s2)) || (!isEvenString(s1) && isEvenString(s2))))
                s2 = s2.concat(s2.substring(0,1));

            /*
            if s1 and s2 are both even or both odd lengths then place s2 in middle of s1
             */
            int start = s1.length()/2 - s2.length()/2;
            int end = start + s2.length();
            if((isEvenString(s1) && isEvenString(s2)) || (!isEvenString(s1) && !isEvenString(s2))) {
                palindromicSubstring =
                        buildPalindrome(new StringBuilder(s1).replace(start, end, s2).toString(), true);
                return palindromicSubstring;
            }
        }

        /*
        Try placing s2 at each position in s1 and calculate the cost of such a placement. However, substring should not
        be placed such that it crosses the middle of s1 (If so, then part of substring s2 will be lost).
        Finally, return the placement with minimum cost (replacement operations).
         */
        while(i <= s1.length()-s2.length()){

            // place s2 at each position on left half of s1
            if((isEvenString(s1) && i+s2.length()-1 < s1.length()/2) ||
                    (!isEvenString(s1) && i+s2.length()-1 <= s1.length()/2))
                s1Pal = buildPalindrome(new StringBuilder(s1).replace(i, i+s2.length(), s2).toString(), true);

                // place s2 at each position on right half of s1
            else
                s1Pal = buildPalindrome(new StringBuilder(s1).replace(i, i + s2.length(), s2).toString(), false);

            cost = getCost(s1, s1Pal);
            if (cost < minCost){
                minCost = cost;
                minCostPos = i;
            }

            i += 1;
            if(i+s2.length()-1 == s1.length()/2)
                i = s1.length()/2;
        }

        if(minCostPos < s1.length()/2)
            palindromicSubstring = buildPalindrome(new StringBuilder(s1).replace(minCostPos, minCostPos + s2.length(), s2).toString(), true);
        else
            palindromicSubstring = buildPalindrome(new StringBuilder(s1).replace(minCostPos, minCostPos + s2.length(), s2).toString(), false);

        return palindromicSubstring;
    }


    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        System.out.print("Input s1: ");
        String s1 = in.nextLine();
        System.out.print("Input s2: ");
        String s2 = in.nextLine();

        String out = getPalindromicSubstring(s1, s2);
        System.out.println(out);

        if(out.equals(""))
            System.out.println("-1");
        else
            System.out.println(getCost(out, s1));

    }
}