0

Let's say,

string1 = "abijkabccbakfgba"
sub_string = "abcd"

I have to ensure that sub_string is present in string1 and find all possible available palindromes without altering overall length of string.

Palindrome can be made to "abcdkabccbakdcba" , with minimum number of substitutions and ensuring provided sub_string exists in string1.

How can we find optimal solution that can handle even larger length of string ?

def func(string1, sub_string):
   if string1 == string1[::-1]:
      if sub_string in string1:
          print("Valid with zero substitutions")
      else:
           # replace missing substring to make it palindrome
           # If portion of sub_string exists, let's continue from there
           # If none exists, let's replace any characters to match it to sub_string
   else:
        # Make it palindrome ensuring sub_string exists with less number of substitutions

Any better approach or any specific algorithm keeping time complexity and space complexity ?

1) Make string1 palindrome. 
2) Ensure that sub_string exists in string1. 
3) Find the least number substitutions used to make it palindrome.

string1 = "rstutir"
string1 = list(string1)
sub_string = "abc"
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]

However palindrome can be achieved by above code. What's best way to ensure sub_string in string1 ?

EDITED: Same question Convert given string to Palindrome with given substring

Hope you get better view of question now.

StackGuru
  • 471
  • 1
  • 9
  • 25
  • Can you substitute any character in string1 with any character of your choice? Or are you restricted to replace any part of string1 having the same length as sub_string with sub_string? The problem as it is described is not clear and you would be better off posting the original problem statement. – Tarik Aug 16 '20 at 03:18
  • Sorry for that. 1) Make string1 palindrome. 2) Ensure that sub_string exists in string1. Find the least number substitutions used to make it palindrome. – StackGuru Aug 16 '20 at 03:25
  • Am I clear now ? Please let me know, If I'm not clear. I can improve my explanation. – StackGuru Aug 16 '20 at 03:25
  • 1
    Say I have rstuutir as string1 and abc as substring. Is there a solution? Am I allowed to substitute i by s? Can I substitute any part of string1 by abc and also cba or am I restricted to use abc as is, in which case, I have no guarantee that I can firm a palindrome. – Tarik Aug 16 '20 at 03:34
  • 1
    Got it. Now the code you are showing does nothing. Why don't you implement your idea first? I see nothing in your code that provides enough details to get things done. You have to understand that SO does not code for people and do not do their homework. – Tarik Aug 16 '20 at 03:44
  • @Tarik Example: if string1="ddddd" and sub_string="eee", then palindrome string is "deeed" and substitutions = 3 – StackGuru Aug 16 '20 at 03:44
  • @Tarik Thank you. I'm trying it but not getting it. – StackGuru Aug 16 '20 at 03:46
  • Step 1: Loop through the first half of the string and compare each character with the one in the opposite side to determine which characters need to be substituted. You can keep a list of positions. Step 2: Check if substring is already in there. If so, just do the substitutions necessary to make it a palindrome. If not, find the largest contiguous area that needs substitution and use substring as replacement characters. – Tarik Aug 16 '20 at 03:49
  • @Tarik Thanks for your suggestion. That's basic and yes i have implemented that part already. Now, the question comes how to handle the substring in string1. May be no portion of substring in string1. May be portion of substring in string1. – StackGuru Aug 16 '20 at 03:52
  • @Tarik Could think of anything ? – StackGuru Aug 16 '20 at 04:12
  • Provided you with a general overview of what to do. Start coding to learn. – Tarik Aug 16 '20 at 04:21
  • Well, Thanks for your suggestion. – StackGuru Aug 16 '20 at 04:22
  • @Tarik You seem to be very helpful in assisting. test="abcdefggfedcba" , sub_string="ifg". sub_string not present in test. But portion of sub_string it exists test. So, here if change just two characters ('e' from efg/gfe) that would be palindrome and ensuring sub_string 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 ? – StackGuru Aug 18 '20 at 17:07
  • @Tarik Refer this https://stackoverflow.com/questions/54959424/convert-given-string-to-palindrome-with-given-substring. Could think of anything now ? Hope you have got some idea now. – StackGuru Aug 18 '20 at 17:24

0 Answers0