Перейти к: навигация, поиск
```from collections import defaultdict
from typing import Dict, List

class Solution:
def removeDuplicateLetters(self, s: str) -> str:
if len(s) == 0:
return ''

letter_positions = self.find_letter_positions(s)

position_letters = dict()

for l, positions in letter_positions.items():
for p in positions:
position_letters[p] = l

letters = sorted(set(s))
result = ''

current_position = 0

while len(letters) > 0:
i = 0
is_letter_chosen = False

while i < len(letters):
l = letters[i]
positions = [k for k in letter_positions[l] if k >= current_position]

for p in positions:
if not self.can_take_letter(l, p, letters, position_letters):
continue

result += l
current_position = p

is_letter_chosen = True
letters.remove(l)

break

if len(letters) == 0:
break

if is_letter_chosen:
current_position = min(k for k in position_letters if k > p)  # TODO: optimize

break

i += 1

assert is_letter_chosen

return result

def find_letter_positions(
self,
s: str) -> Dict[str, List[int]]:

if len(s) == 0:
return dict()

result = defaultdict(list)

i = 0
current_letter = s[0]

result[current_letter].append(0)

i += 1

while i < len(s):
while i < len(s) and s[i] == current_letter:
i += 1

if i == len(s):
break

current_letter = s[i]
result[current_letter].append(i)

return result

def can_take_letter(
self,
letter: str,
current_position: int,
letters: List[str],
position_letters: Dict[int, str]) -> bool:

return (
set([l for p, l in position_letters.items() if p >= current_position]) >= set(letters)
)```