1209. Remove All Adjacent Duplicates in String II

Prompt

You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

Input: s = "deeedbbcccbdaa", k = 3 Output: "aa" Explanation:  First delete "eee" and "ccc", get "ddbbbdaa" Then delete "bbb", get "dddaa" Finally delete "ddd", get "aa"
  • 2 <= k <= 104
  • s only contains lowercase English letters.

Approach

Once we’ve detected a character to appear k times in the given string, then we want to simply remove that character. The scenario in which we need to account for is if a group of k duplicate characters emerges subsequent to a removal of k characters from our given string (as depicted by the example above).

Code

Python | Time: O(n) where there will be in-total n insertions and deletions from our Stack | Space: O(n) where n is the # of characters in the given string s

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
John Kim

John Kim

75 Followers

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com