Блог пользователя anshu2002

Please solve my doubt
Автор anshu2002, история, 2 года назад, По-английски

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

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          → Ответить
»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

→ Ответить
»
2 года назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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!

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить