anshu2002's blog

By anshu2002, history, 6 months 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

»
6 months 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.

  • »
    »
    6 months 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

    • »
      »
      »
      6 months 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.

»
6 months 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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 months 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.

      • »
        »
        »
        »
        6 months 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

        • »
          »
          »
          »
          »
          6 months 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.

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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)

            • »
              »
              »
              »
              »
              »
              »
              6 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ok I need to process that for sometime

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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)

»
6 months 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...

»
6 months 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!

  • »
    »
    6 months 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.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, thank you for the correction!

    • »
      »
      »
      6 months 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).

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months 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)$$$.