How to calculate the number of times you need to change one string to another string?

Question

Lets say I have 2 strings:

String1 = "ABBABBAA"
String2 = "ABBAABBB"

I want to turn String2 into String1. I can only change the string one at a time. My goal is that I want to figure out the number of times it will take me to change string2 into string1.

Also note that if two characters that need to be changed are next to eachother, count that as 1. Here is what I mean:

string1 = "GHGGH"
string2 = "HGGGH"

As you can see, I only need to change characters 1 and 2 in string2. Since characters 1 and 2 are next to eachother, I will count that as one turn. So the answer would be 1.

Now I will show you how to turn string2 into string1 from the example at the top:

String1 = "ABBABBAA"
String2 = "ABBAABBB"

In this example, You need to change string 5 and strings 7 and 8 in String2. The output would be 2, because one turn comes from 5, and the second turn comes from 7 and 8 since they are next to eachother.

Output:
>> 2

(Also I am a little new to Stack Overflow, so please excuse me if I may have written my question in bad formatting.)

I dont want to make string1 equal to string 2. I simply just want to find the number of times it takes to change string 1 into string 2, step by step. — Eren145, Feb 23 '20 at 20:16
welcome to stack overflow, if the goal is to change each character one at a time then there could be more than one way of just changing one character just considering time complexity here..? — de_classified, Feb 23 '20 at 20:17
Yes I do want to consider time complexity, so maybe an effective way to change the characters one at a time. Would .replace() be considered effective? Sorry, I am not very familiar with time complexity yet. — Eren145, Feb 23 '20 at 20:18
strings are immutable, so at each step, you have a completely new string — kederrac, Feb 23 '20 at 20:18
True, but that is not what I am asking for. I just want to print how many times it will take to change string 1 into string 2 one character at a time. — Eren145, Feb 23 '20 at 20:20
But as @FishingCode pointed out, the way you count swapping etc as 1 operation makes it so there is not one clear answer, as swapping still changes two characters of the string. — Eric, Feb 23 '20 at 20:23
Just to be clear: You are asking how to calculate *string distances*? What algorithms have you researched and what code have you tried? What specific problems did you encounter and need help with? — MisterMiyagi, Feb 23 '20 at 20:27
Does this answer your question? [String similarity metrics in Python](https://stackoverflow.com/questions/1471153/string-similarity-metrics-in-python) — MisterMiyagi, Feb 23 '20 at 20:30
What's the correct answer for String1 = "AB" and String2 = "CD"? — Kelly Bundy, Feb 23 '20 at 20:50
1, since the characters that need to be changed in string2, are next to eachother. — Eren145, Feb 23 '20 at 21:13

CarlosSR · Accepted Answer · 2020-02-23T20:25:45.220

1

Probably it can be optimised somehow but you have to check each string per position and acknowledge if the previous position was different or not

def compare(a, b):
  i=0
  prev_diff=0
  for x, y in zip(a, b):
    if x != y and prev_diff==0:
        prev_diff=1
        i += 1
    elif x!=y and prev_diff==1:
        prev_diff=1
    else:
        prev_diff=0
  print(i)

compare(String1,String2)
Out: 2

edited Feb 23 '20 at 20:25

answered Feb 23 '20 at 20:24

CarlosSR

1,145
1
10
22

Thank you. This code seems to work. I made a few changes to meet my desired output, but thanks for this format. – Eren145 Feb 23 '20 at 20:33

kederrac · Answer 2 · 2020-02-23T22:08:16.953

0

you can use:

from itertools import groupby

sum(1 if k1 != k2 or len(list(v1)) != len(list(v2)) else 0
     for (k1, v1), (k2, v2) in zip(groupby(String1), groupby(String2)))

edited Feb 23 '20 at 22:08

answered Feb 23 '20 at 20:23

kederrac

16,819
6
32
55

How to calculate the number of times you need to change one string to another string?

2 Answers2