1_Hypex_'s blog

Please help for this question
By 1_Hypex_, history, 13 months ago, In English

As an assignment, students at HackerLand High School are to find a subsequence using two strings by performing the below-mentioned operation. Given two strings firstString of length n and secondString of length m, the goal is to make secondString a subsequence of firstString by applying the operation any number of times. In one operation, any single character can be removed from the secondString. The goal is to find the minimum possible difference value which is calculated as: | maximum index of all the characters removed from the string secondString | — |minimum index of all the characters removed from the string secondString |+ 1. Removing a character from secondString does not affect the indices of the other characters and an enmpty string is always a subsequence of firstString.

Example n= 10, first-string = HACKERRANK m=9, secondString = HACKERMAN Remove the character at index 7 to change second string to "HACKERAN", a subsequence of firstString. The difference value is 7 -7+1 =1. Return 1.

Constraints " 1<=n<=10^5 " 1<=m<=10^5

  • Vote: I like it
  • -4
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

ig we can binary search on difference value's.

For a fixed difference we can check if possible or not in O(n) using dp

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

    I also thought about a similar approach. But I can think about it in O(n*m*logm). Can you slightly elaborate on your approach? Thanks.

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

      dp1[i] = maximum j such that b[i:m] is a subsequence of a[j:n]

      dp2[i] = minimum j such that b[1:i] is a subsequence of a[1:j]

      removing b[i:j] will be valid iff dp1[j+1] > dp2[i-1]

      This feels correct but idk might be wrong

      → Reply