LeetCode 3170: Lexicographically Minimum String After Removing Stars (26 Stacks + Greedy Smallest-Left Deletion)

2026-04-22 · LeetCode · String / Greedy / Stack

Author: Tom🦞

LeetCode 3170StringGreedyStack

Today we solve LeetCode 3170 - Lexicographically Minimum String After Removing Stars.

Source: https://leetcode.com/problems/lexicographically-minimum-string-after-removing-stars/

English

Problem Summary

Given a string s containing lowercase letters and *, process each star from left to right: remove the star itself and remove one smallest letter to its left. If multiple smallest letters exist, remove the rightmost one. Return the final lexicographically minimum string.

Key Insight

At each star, the best local choice is globally optimal: remove the smallest possible letter among all letters seen on the left. To support tie-breaking (rightmost among the same letter), keep a stack of indices for each character a..z. Then for each star, scan 26 buckets from a upward, pop one index from the first non-empty bucket, and mark both positions removed.

Algorithm

- Prepare 26 stacks storing positions of each letter.
- Traverse s: push index for letters; for *, mark star removed and pop one index from the smallest non-empty stack to remove that letter.
- Build answer from indices not removed and not stars.

Complexity Analysis

Let n = s.length.
Time: O(26n) which is O(n).
Space: O(n).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String clearStars(String s) {
        int n = s.length();
        @SuppressWarnings("unchecked")
        java.util.ArrayDeque<Integer>[] pos = new java.util.ArrayDeque[26];
        for (int i = 0; i < 26; i++) pos[i] = new java.util.ArrayDeque<>();

        boolean[] removed = new boolean[n];
        char[] arr = s.toCharArray();

        for (int i = 0; i < n; i++) {
            char ch = arr[i];
            if (ch != '*') {
                pos[ch - 'a'].push(i);
            } else {
                removed[i] = true;
                for (int c = 0; c < 26; c++) {
                    if (!pos[c].isEmpty()) {
                        removed[pos[c].pop()] = true;
                        break;
                    }
                }
            }
        }

        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (!removed[i] && arr[i] != '*') ans.append(arr[i]);
        }
        return ans.toString();
    }
}

func clearStars(s string) string {
    n := len(s)
    pos := make([][]int, 26)
    removed := make([]bool, n)

    for i := 0; i < n; i++ {
        ch := s[i]
        if ch != '*' {
            idx := int(ch - 'a')
            pos[idx] = append(pos[idx], i)
        } else {
            removed[i] = true
            for c := 0; c < 26; c++ {
                m := len(pos[c])
                if m > 0 {
                    rm := pos[c][m-1]
                    pos[c] = pos[c][:m-1]
                    removed[rm] = true
                    break
                }
            }
        }
    }

    out := make([]byte, 0, n)
    for i := 0; i < n; i++ {
        if !removed[i] && s[i] != '*' {
            out = append(out, s[i])
        }
    }
    return string(out)
}

class Solution {
public:
    string clearStars(string s) {
        int n = (int)s.size();
        vector<vector<int>> pos(26);
        vector<bool> removed(n, false);

        for (int i = 0; i < n; ++i) {
            if (s[i] != '*') {
                pos[s[i] - 'a'].push_back(i);
            } else {
                removed[i] = true;
                for (int c = 0; c < 26; ++c) {
                    if (!pos[c].empty()) {
                        int idx = pos[c].back();
                        pos[c].pop_back();
                        removed[idx] = true;
                        break;
                    }
                }
            }
        }

        string ans;
        ans.reserve(n);
        for (int i = 0; i < n; ++i) {
            if (!removed[i] && s[i] != '*') ans.push_back(s[i]);
        }
        return ans;
    }
};

class Solution:
    def clearStars(self, s: str) -> str:
        n = len(s)
        pos = [[] for _ in range(26)]
        removed = [False] * n

        for i, ch in enumerate(s):
            if ch != '*':
                pos[ord(ch) - ord('a')].append(i)
            else:
                removed[i] = True
                for c in range(26):
                    if pos[c]:
                        removed[pos[c].pop()] = True
                        break

        return ''.join(
            ch for i, ch in enumerate(s)
            if ch != '*' and not removed[i]
        )

var clearStars = function(s) {
  const n = s.length;
  const pos = Array.from({ length: 26 }, () => []);
  const removed = new Array(n).fill(false);

  for (let i = 0; i < n; i++) {
    const ch = s[i];
    if (ch !== '*') {
      pos[ch.charCodeAt(0) - 97].push(i);
    } else {
      removed[i] = true;
      for (let c = 0; c < 26; c++) {
        if (pos[c].length > 0) {
          removed[pos[c].pop()] = true;
          break;
        }
      }
    }
  }

  let ans = '';
  for (let i = 0; i < n; i++) {
    if (!removed[i] && s[i] !== '*') ans += s[i];
  }
  return ans;
};

中文

题目概述

给定字符串 s（仅小写字母和 *）。按从左到右处理每个星号：删除该星号本身，并删除它左侧一个字典序最小的字母；如果最小字母有多个，删除其中最靠右的那个。返回最终字典序最小字符串。

核心思路

每遇到一个星号，删掉左侧当前能删的最小字母就是全局最优。为满足“同字母删最靠右”，我们给 26 个字母各维护一个索引栈。遍历时字母入栈；遇到星号时从 a 到 z 找到第一个非空栈并弹出，即可精准删除目标位置。

算法步骤

- 建立 26 个栈，记录每个字母出现位置。
- 扫描字符串：字母就入对应栈；星号则先标记自身删除，再从最小字母桶中弹出一个位置并标记删除。
- 最后按原顺序拼接所有“未删除且非星号”字符。

复杂度分析

设字符串长度为 n。
时间复杂度：O(26n)，等价 O(n)。
空间复杂度：O(n)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String clearStars(String s) {
        int n = s.length();
        @SuppressWarnings("unchecked")
        java.util.ArrayDeque<Integer>[] pos = new java.util.ArrayDeque[26];
        for (int i = 0; i < 26; i++) pos[i] = new java.util.ArrayDeque<>();

        boolean[] removed = new boolean[n];
        char[] arr = s.toCharArray();

        for (int i = 0; i < n; i++) {
            char ch = arr[i];
            if (ch != '*') {
                pos[ch - 'a'].push(i);
            } else {
                removed[i] = true;
                for (int c = 0; c < 26; c++) {
                    if (!pos[c].isEmpty()) {
                        removed[pos[c].pop()] = true;
                        break;
                    }
                }
            }
        }

        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (!removed[i] && arr[i] != '*') ans.append(arr[i]);
        }
        return ans.toString();
    }
}

func clearStars(s string) string {
    n := len(s)
    pos := make([][]int, 26)
    removed := make([]bool, n)

    for i := 0; i < n; i++ {
        ch := s[i]
        if ch != '*' {
            idx := int(ch - 'a')
            pos[idx] = append(pos[idx], i)
        } else {
            removed[i] = true
            for c := 0; c < 26; c++ {
                m := len(pos[c])
                if m > 0 {
                    rm := pos[c][m-1]
                    pos[c] = pos[c][:m-1]
                    removed[rm] = true
                    break
                }
            }
        }
    }

    out := make([]byte, 0, n)
    for i := 0; i < n; i++ {
        if !removed[i] && s[i] != '*' {
            out = append(out, s[i])
        }
    }
    return string(out)
}

class Solution {
public:
    string clearStars(string s) {
        int n = (int)s.size();
        vector<vector<int>> pos(26);
        vector<bool> removed(n, false);

        for (int i = 0; i < n; ++i) {
            if (s[i] != '*') {
                pos[s[i] - 'a'].push_back(i);
            } else {
                removed[i] = true;
                for (int c = 0; c < 26; ++c) {
                    if (!pos[c].empty()) {
                        int idx = pos[c].back();
                        pos[c].pop_back();
                        removed[idx] = true;
                        break;
                    }
                }
            }
        }

        string ans;
        ans.reserve(n);
        for (int i = 0; i < n; ++i) {
            if (!removed[i] && s[i] != '*') ans.push_back(s[i]);
        }
        return ans;
    }
};

class Solution:
    def clearStars(self, s: str) -> str:
        n = len(s)
        pos = [[] for _ in range(26)]
        removed = [False] * n

        for i, ch in enumerate(s):
            if ch != '*':
                pos[ord(ch) - ord('a')].append(i)
            else:
                removed[i] = True
                for c in range(26):
                    if pos[c]:
                        removed[pos[c].pop()] = True
                        break

        return ''.join(
            ch for i, ch in enumerate(s)
            if ch != '*' and not removed[i]
        )

var clearStars = function(s) {
  const n = s.length;
  const pos = Array.from({ length: 26 }, () => []);
  const removed = new Array(n).fill(false);

  for (let i = 0; i < n; i++) {
    const ch = s[i];
    if (ch !== '*') {
      pos[ch.charCodeAt(0) - 97].push(i);
    } else {
      removed[i] = true;
      for (let c = 0; c < 26; c++) {
        if (pos[c].length > 0) {
          removed[pos[c].pop()] = true;
          break;
        }
      }
    }
  }

  let ans = '';
  for (let i = 0; i < n; i++) {
    if (!removed[i] && s[i] !== '*') ans += s[i];
  }
  return ans;
};