anshu2002's blog

Please solve my doubt
By anshu2002, history, 2 years ago, In English

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

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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:

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s1, s2; cin >> s1 >> s2;
    int l = 0;
    
    for (char c : s1) {
        if (c == s2[l]) l++;
        
        if (l >= s2.length()) break;
    }
    cout << s2.length() - l << "\n";
    
    return 0;
}

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

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)$$$.

→ Reply