the question is , two strings are given s1 and s2 . You have to find minimum number of insertions to be done at the end of s1 so that s2 becomes a subsequence of s1

test #1 s1: armaze s2: amazon ans : 2

test #2 s1: armazen s2: amazon ans : 2

# | User | Rating |
---|---|---|

1 | Benq | 3813 |

2 | tourist | 3768 |

3 | maroonrk | 3570 |

4 | Radewoosh | 3535 |

5 | fantasy | 3526 |

6 | jiangly | 3523 |

7 | Um_nik | 3522 |

8 | orzdevinwang | 3441 |

9 | cnnfls_csy | 3427 |

10 | zh0ukangyang | 3423 |

# | User | Contrib. |
---|---|---|

1 | awoo | 180 |

2 | -is-this-fft- | 178 |

3 | nor | 169 |

4 | Um_nik | 168 |

5 | SecondThread | 164 |

6 | maroonrk | 163 |

6 | adamant | 163 |

8 | kostka | 161 |

9 | YouKn0wWho | 158 |

10 | antontrygubO_o | 155 |

the question is , two strings are given s1 and s2 . You have to find minimum number of insertions to be done at the end of s1 so that s2 becomes a subsequence of s1

test #1 s1: armaze s2: amazon ans : 2

test #2 s1: armazen s2: amazon ans : 2

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/29/2023 18:43:00 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

You haven't defined subsequence so I am using this definition: A subsequence of a string (let's call the string a) is a string that can be produced by deleting zero or more characters from a in any position.

We want to find the biggest prefix of s2 that is already a subsequence of s1. To do this:

loop through s1, and keep a pointer to the letter in s2 that we want to find in s1. Once we find it, increment the counter..

At the end of the loop the counter will show how the length of the largest prefix of s2 that is a subsequence of s1, call this variable length. The answer will then simply be s2.length() — length.

I may be wrong so don't be afraid to correct me or point out my mistake. I've only thought about this question for about 5 minutes.

see . The issue here is TC . s1 and s2 maybe of 10^5 . And the method you are suggesting may have the TC of O(n*n) . So in that case it will show tle

Sorry if i didn't explain myself clearly.

My solution is only O(n). I am only looping through s1 ONCE. not n times. Let me explain again. You keep two pointers, one at the start of s1, and one at the start of s2.

while (s1_pointer < s1.length() and s2_pointer < s2.length()) { if pointer at s1 equals pointer at s2 then increment s2_pointer increment s1 }

I have used this format to explain my algorithm so that it would be easier to understand. The s2 pointer is the element in s2 that i am currently looking for. Notice that I don't want to find this element before the s1_pointer because before that, i have not found the previous elements of s2 yet. In fact this code is so simple i will write it right here.

string s1, s2; cin >> s1 >> s2; int s1_pointer = 0, s2_pointer = 0;

while(s1_pointer < s1.length() && s2_pointer < s2.length()) { if (s2[s2_pointer] = s1[s1_pointer]) s2_pointer++; s1_pointer++; }

cout << s2.length() — s2_pointer << endl;

As you can see, this code is clearly O(n) because I am only iterating through s1 once.

just solve it with greedy. Iterate through s2 for each letter here find the first matching from previous matching (start from 0) then s2.size — maximum_match is the answer

is the tc O(n*n) . Then it's a problem

It's O(n). You start from the first character in s2 and try to find the matching character in s1. When you do, move to the next character in s2 and try to find it in s1 but to the right of the previous matched character. You do this until you run out of characters in s2 or s1.

What if multiple instances present in s1 for a particular character of s2

You stop at the first character in s1 that matches the character in s2, because it is always better to do so.

Ya I am getting that . Thank u . That's why you are an expert . Otherwise I was thinking of applying LCS which would result O(n*n)

There is a standard way to check if A is a subsequence of B or not. You just need to check how much prefix part of A is a subsequence of B.

What does being an expert relate here? The question is hardly 900-1000 rated on CF.

Ok I need to process that for sometime

just adding to this you could also go for binary search + LCS like take the string s2 and iterate on its length for eg: we calculate the mid value and check if the there exists a subsequence s2[0...mid] in s1 (check if the length of LCS equals our prefix s2(0...mid). then we finally print s1.size() — ans.

You may find how many character from s2 matches in s1 (for sure with respect for their ordering in s2 and s1) that would take O(n).like what catsareliquid said ^_^

then the needed characters to be inserted will be size of s2 — the total characters we found in the first place.. time complexity O(1)

so total time complexity would be O(n)

Why is the article being downvoted? The author is just asking a question...

We can solve this in O(n) where n is the length of s1 —

The main idea is to have a pointer, say L, which is equal to the beginning of s2. Then, we can iterate through each character in s1 and whenever s1[i] == s2[L], can can just increment L. After the for loop finishes or L >= m, the pointer will be at the beginning of the substring that needs to be added. You can either print out (m — L) or print the substring: whatever floats your boat.

Here's my code for reference:

P.S I just wanted to help a bit! Sorry about the overlapping ideas in TheOpChicken123 response!

Your code is actually just O(n) not O(n+m) because you are only looping through s1 once, and not s2.

Yes, thank you for the correction!

actually you need to take the second string as input. So that makes it O(n + m).

Just curious, what would happens if this was modified so that you can insert anywhere in s1? Edit: Nvm figured it out, it'll just be the difference between the strings' counters.

First, you check for the first element of s2 in s1, if yes, go ahead to the second, the third, etc. If you reach the end of s1, print out the number of remaining characters in s2. This greedy method can be done in O(max(s1.length, s2.length))

I think you may try doing it with $$$2 pointer$$$. Just count the $$$max$$$ $$$length$$$ of $$$prefix$$$ of $$$s2$$$ you may get from $$$s1$$$ after removing some character than just answer it by $$$s2.size() - MaxPrefixLength$$$.

To get $$$MaxPrefixLength$$$ use $$$2 pointer$$$. $$$TimeComplexity : O(n)$$$.