Shortest subsequence


  • 0
    S

    Given two strings S1 and S2, find the shortest subsequence in S1 that contains all the characters in S2.
    Note: the order in which S2's characters appear in S1 does not matter

    Ex:
    S1 = "ABCKLADEKCLB"
    S2 = "BEK"

    shortest subsequence is "EKCLB"


  • 0
    C
    • For each char in s2, use an array to store positions of that character in s1
    • The problem becomes: given a list of sorted arrays, find the minimum range contains at least one number from each array.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.