How to convert string to palindrome, provided substring should exist in palindrome string ?

Question

1.00/5 (1 vote)

See more:

Given a String S1 and String S2. Convert string S1 to a palindrome string such S2 is a substring of that palindromic string. This conversion must be done by using minimum number pf operations.
              You are allowed to use only one operation in which you can replace any character of string S1 with any other character. his operation can be used any number of times.

I have written normal code to make it as palindrome by replacing characters. I'm not getting how to write the logic to replace substring elements in string.
1) 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.
2)  test="abcdefggfedcba" , sub_string="ifg". sub_string not present in test. But portion of sub_string it exists test. So, here have to change just two characters ('e' from efg/gfe) that would be palindrome and ensuring sub_string in test as well. What's efficient way to handle it ? I see, str.find(sub_string). But it's hard to find as in above case. Any thoughts ?

What I have tried:

Python

string1 = "rstutir"
#string1 = list(string1)
sub_string = "abc"
if string1 == string1[::-1]:
   if sub_string in string1:
      print("Valid palindrome and sub string exists")   
   else:
        # How to make sure sub_string exists in string
        # with less number of operations
else:
   count = 0
   for i in range(len(string1)//2): 
        if(string1[i]== string1[n-i-1]): 
            continue

        count += 1
  
        if(string1[i]<string1[n-i-1]): 
            string1[n-i-1]= string1[i] 
        else: 
            string1[i]= string1[n-i-1]

Posted 18-Aug-20 11:50am

stackguru

Updated 18-Aug-20 14:15pm

Add a Solution

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Patrice T · Answer 1 · 2020-08-18T14:15:00

Quote:
But it's hard to find as in above case. Any thoughts ?

Don't try to find a magic trick, for such a problem, go brute force.
Brute force is to try every possibilities.

Python

for any possible position of s2 in s1
  reset changes counter
  do necessary changes to have s2 in s1
  do necessary changes to make s1 a palindrome (without changing the place holding s2)
  if changes is better than previous tries, set the new minimum.

[update]

Quote:
How do you manage that 'any possible position of s2 in s1' ?

With input test="abcdefggfedcba" , sub_string="ifg"

Python

for any possible position of s2 in s1

gives

ifgdefggfedcba
aifgefggfedcba
abifgfggfedcba
abcifgggfedcba
abcdifggfedcba
abcdeifgfedcba
abcdefifgedcba
abcdefgifgdcba
abcdefggifgcba
abcdefggfifgba
abcdefggfeifga
abcdefggfedifg

Quote:
If length of sub_string is very long and then most of time consumed i checking what portion of sub_string exists. correct ? Any efficient way ? What could be the solution ?

There is no magic, if there is a better way, you need a good knowledge of the problem, and experiment different solutions and see what works best.
What is best solution for this

Python

test="abcfgfaba" , sub_string="ifg"
test="abcfgfaba" , sub_string="gfi"