Convert one string to another given constraints

Question

Given 2 strings, s1 and s2. Len(s2) < len(s1).

Both strings have only “a” and “b” characters. Given 2 operations:

s2 = s2 + “a”
s2 = rev(s2) + “b”

Find if by doing the above 2 operations, s2 will be equal to s1 ever.

I can only think of the naive solution where we can recursively perform the two mentioned operations on s2 and whenever length of the two strings become equal we can check if s2 = s1.

But the time complexity of the naive solution is exponential : (2^len_diff), where len_diff is the difference of the lengths of the two strings.

Is there a better solution for this?

@abhay no this is not from any contest. I was asked this question in an interview. — tom
– tom, Commented Nov 10, 2020 at 1:38

user58697 · Accepted Answer · 2020-11-09 17:49:48Z

2

Work backwards. Instead of building s1 from s2, strip characters from the end of s1. This way you know for sure which operation to undo. If you eventually end up with s2, you are done.

answered Nov 9, 2020 at 17:49

user58697

8,0481 gold badge16 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

tom Over a year ago

This seems to be the simplest answer, and there also does not seems to be anything wrong with it. Can someone confirm if this is the correct answer?

NoShady420 · Accepted Answer · 2020-11-10 10:53:02Z

0

So assuming the answer exists, s1 will either be of form:

(s₂a*), (a*bs₂a*ba*), (a*ba*bs₂a*ba*ba*),...

or of form

(a*s'₂ba*), (a*ba*s'₂ba*ba*),...

where s'₂ is the reverse of s₂

So your question reduces to finding whether the regular expression

s₁ = [(a*b)ⁿ s₂ (a*b)ⁿ a*] V [a* (ba* )ⁿ s'₂ (ba*)ⁿ⁺¹]

holds true. You could use a regex library to parse and check it

If have to write the parsing algorithm ground up, you wouldn't even have to check for a*. You could get away with merely counting the number of b's to either side of s₂

A pseudocode would be something like

B1 = number of b's in s2 //O(n)
B2 = number of b's in s1 //O(n)

//Locate s2 in s1 and check b_left = b_right and character before s2 is b

b_to_left = 0

for i from 1 to (s1's length - s2's length): //O(n iteration)
    if s2.length characters of s1 starting at index i DO NOT match s2: //At worse O(n to check)
        if(s1[i] is b) b_to_left++
        continue to next i

    b_to_right = B1 - B2 - b_to_left
    if(b_to_left == b_to_right) :
        if(b_to_left == 0)  RETURN TRUE
        else if(s[i-1] is b) RETURN TRUE
    
    if(s1[i] is b) b_to_left++


//Similarly run another round and parse for the second type involving reverse of s2
//I'm leaving that out as an exercise for you since you mentioned it's an interview problem 




RETURN FALSE

Time: O(n²)

Space: O(1)

answered Nov 10, 2020 at 10:53

NoShady420

9416 silver badges17 bronze badges

1 Comment

tom Over a year ago

Yeah it seems to be the correct approach, just wondering if the answer by user58697 is correct, in that case that would be the simplest answer with O(n) time complexity. Also the interview was over before I posted the question. I could not answer in the interview.

Collectives™ on Stack Overflow

Convert one string to another given constraints

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related