Remove Duplicate Letters LeetCode Solution | Easy Approach

Minimum Cost to Merge Stones
Share:

Remove Duplicate Letters Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

Constraints:

  • 1 <= s.length <= 104
  • s consists of lowercase English letters.

Remove Duplicate Letters Solutions

Time: O(n)
Space: O(n)

C++

class Solution {
 public:
  string removeDuplicateLetters(string s) {
    string ans;
    vector<int> count(128);
    vector<bool> used(128);

    for (const char c : s)
      ++count[c];

    for (const char c : s) {
      --count[c];
      if (used[c])
        continue;
      while (!ans.empty() && ans.back() > c && count[ans.back()] > 0) {
        used[ans.back()] = false;
        ans.pop_back();
      }
      used[c] = true;
      ans.push_back(c);
    }

    return ans;
  }
};

Java

 class Solution {
  public String removeDuplicateLetters(String s) {
    StringBuilder sb = new StringBuilder();
    int[] count = new int[128];
    boolean[] used = new boolean[128];

    for (final char c : s.toCharArray())
      ++count[c];

    for (final char c : s.toCharArray()) {
      --count[c];
      if (used[c])
        continue;
      while (sb.length() > 0 && last(sb) > c && count[last(sb)] > 0) {
        used[last(sb)] = false;
        sb.setLength(sb.length() - 1);
      }
      used[c] = true;
      sb.append(c);
    }

    return sb.toString();
  }

  private char last(StringBuilder sb) {
    return sb.charAt(sb.length() - 1);
  }
}

Python


class Solution:
  def removeDuplicateLetters(self, s: str) -> str:
    ans = []
    count = Counter(s)
    used = [False] * 26

    for c in s:
      count[c] -= 1
      if used[ord(c) - ord('a')]:
        continue
      while ans and ans[-1] > c and count[ans[-1]] > 0:
        used[ord(ans[-1]) - ord('a')] = False
        ans.pop()
      ans.append(c)
      used[ord(ans[-1]) - ord('a')] = True

    return ''.join(ans)

Watch Tutorial

Checkout more Solutions here

Leave a Comment

Your email address will not be published. Required fields are marked *

x