{"id":8567,"date":"2021-08-11T19:40:40","date_gmt":"2021-08-12T02:40:40","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8567"},"modified":"2021-08-11T19:41:52","modified_gmt":"2021-08-12T02:41:52","slug":"leetcode-1898-maximum-number-of-removable-characters","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-1898-maximum-number-of-removable-characters\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1898. Maximum Number of Removable Characters"},"content":{"rendered":"\n

You are given two strings s<\/code> and p<\/code> where p<\/code> is a subsequence <\/strong>of s<\/code>. You are also given a distinct 0-indexed <\/strong>integer array removable<\/code> containing a subset of indices of s<\/code> (s<\/code> is also 0-indexed<\/strong>).<\/p>\n\n\n\n

You want to choose an integer k<\/code> (0 <= k <= removable.length<\/code>) such that, after removing k<\/code> characters from s<\/code> using the first<\/strong> k<\/code> indices in removable<\/code>, p<\/code> is still a subsequence<\/strong> of s<\/code>. More formally, you will mark the character at s[removable[i]]<\/code> for each 0 <= i < k<\/code>, then remove all marked characters and check if p<\/code> is still a subsequence.<\/p>\n\n\n\n

Return the maximum<\/strong> <\/em>k<\/code> you can choose such that <\/em>p<\/code> is still a subsequence<\/strong> of <\/em>s<\/code> after the removals<\/em>.<\/p>\n\n\n\n

A subsequence<\/strong> of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> s = \"abcacb\", p = \"ab\", removable = [3,1,0]\nOutput:<\/strong> 2\nExplanation<\/strong>: After removing the characters at indices 3 and 1, \"ab<\/strong><\/s>ca<\/strong><\/s>cb\" becomes \"accb\".\n\"ab\" is a subsequence of \"a<\/u><\/strong>ccb<\/u><\/strong>\".\nIf we remove the characters at indices 3, 1, and 0, \"ab<\/strong><\/s>ca<\/strong><\/s>cb\" becomes \"ccb\", and \"ab\" is no longer a subsequence.\nHence, the maximum k is 2.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s = \"abcbddddd\", p = \"abcd\", removable = [3,2,1,4,5,6]\nOutput:<\/strong> 1\nExplanation<\/strong>: After removing the character at index 3, \"abcb<\/strong><\/s>ddddd\" becomes \"abcddddd\".\n\"abcd\" is a subsequence of \"abcd<\/strong>dddd\".\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s = \"abcab\", p = \"abc\", removable = [0,1,2,3,4]\nOutput:<\/strong> 0\nExplanation<\/strong>: If you remove the first index in the array removable, \"abc\" is no longer a subsequence.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= p.length <= s.length <= 105<\/sup><\/code><\/li>
  • 0 <= removable.length < s.length<\/code><\/li>
  • 0 <= removable[i] < s.length<\/code><\/li>
  • p<\/code> is a subsequence<\/strong> of s<\/code>.<\/li>
  • s<\/code> and p<\/code> both consist of lowercase English letters.<\/li>
  • The elements in removable<\/code> are distinct<\/strong>.<\/li><\/ul>\n\n\n\n
    Solution: Binary Search + Two Pointers<\/strong><\/h2>\n\n\n\n
    If we don’t remove any thing, p is a subseq of s, as we keep removing, at some point L, p is no longer a subseq of s. e.g [0:True, 1: True, …, L – 1: True, L: False, L+1: False, …, m:False], this array is monotonic. We can use binary search to find the smallest L such that p is no long a subseq of s. Ans = L – 1.<\/p>\n\n\n\n
    For each guess, we can use two pointers to check whether p is subseq of removed(s) in O(n).<\/p>\n\n\n\n
    Time complexity: O(nlogn)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maximumRemovals(string s, string p, vector& removable) {\n    const int n = s.length();\n    const int t = p.length();\n    const int m = removable.size();    \n    int l = 0;\n    int r = m + 1;\n    vector idx(n, INT_MAX);\n    for (int i = 0; i < m; ++i)\n      idx[removable[i]] = i;\n    while (l < r) {\n      int mid = l + (r - l) \/ 2;\n      int j = 0;\n      for (int i = 0; i < n && j < t; ++i)\n        if (idx[i] >= mid && s[i] == p[j]) ++j;      \n      if (j != t)\n        r = mid;\n      else\n        l = mid + 1;\n    }\n    \/\/ l is the smallest number s.t. p is no longer a subseq of s.\n    return l - 1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given two strings s and p where p is a subsequence of s. You are also given a distinct 0-indexed integer array removable containing a subset of indices of s (s is also 0-indexed). You want to choose an integer k (0…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149],"tags":[52,177,229,175],"class_list":["post-8567","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-binary-search","tag-medium","tag-subsequence","tag-two-pointers","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8567","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8567"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8567\/revisions"}],"predecessor-version":[{"id":8569,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8567\/revisions\/8569"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8567"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8567"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8567"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}