String Digit Removal for Lexicographic Order - Greedy String Coding Interview

Question

## Problem Given a string `s` containing lowercase letters and digits, remove exactly `k` digits to produce the lexicographically smallest possible string. Digits must be removed; letters are kept as-is in their relative order. Only digit characters are candidates for removal. ```python def remove_k_digits(s: str, k: int) -> str: ... ``` **Example:** ``` s = "a3b1c2", k = 2 # Digits available: '3','1','2'. Remove 2 of them. # Remove '3' and '2': "ab1c" # Remove '3' and '1': "abc2" # Remove '1' and '2': "a3bc" # Lexicographic comparison: "a3bc" < "ab1c" < "abc2" -- wait, compare char by char. # 'a'='a', then '3' vs 'b': '3'(ASCII 51) < 'b'(ASCII 98) -> "a3bc" is smallest. Output: "a3bc" ``` **Clarification:** Standard lexicographic ordering applies (digits sort before lowercase letters by ASCII). ## Follow-ups - How does this problem change if you can remove any character (not just digits)? (Classic monotonic stack problem -- how does the strategy change?) - What if you want the lexicographically largest string after removing `k` digits? - Extend: remove exactly `k` characters to minimize the numeric value formed by remaining digits (letters ignored).

String Digit Removal for Lexicographic Order - Greedy String Coding Interview

Question Details

Full Details

Topics

More from Codesignal