leetcode 2030. Smallest K-Length Subsequence With Occurrences of a Letter

Python алгоритм LeetCode

ежедневная классика

«Стена в тюрьме» - Тан Ситун (династия Цин)

Ванмэнь проголосовал за то, чтобы перестать думать о Чжан Цзяне, и какое-то время ждал Дугана.

Я улыбнулась небу от горизонтального ножа, и оставила два Куньлуня со своей печенью и желчным пузырем.

описывать

You are given a string s, an integer k, a letter letter, and an integer repetition.

Return the lexicographically smallest subsequence of s of length k that has the letter letter appear at least repetition times. The test cases are generated so that the letter appears in s at least repetition times.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

A string a is lexicographically smaller than a string b if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.

Example 1:

Input: s = "leet", k = 3, letter = "e", repetition = 1
Output: "eet"
Explanation: There are four subsequences of length 3 that have the letter 'e' appear at least 1 time:
- "lee" (from "leet")
- "let" (from "leet")
- "let" (from "leet")
- "eet" (from "leet")
The lexicographically smallest subsequence among them is "eet".

Example 2:

Input: s = "leetcode", k = 4, letter = "e", repetition = 2
Output: "ecde"
Explanation: "ecde" is the lexicographically smallest subsequence of length 4 that has the letter "e" appear at least 2 times.

Example 3:

Input: s = "bb", k = 2, letter = "b", repetition = 2
Output: "bb"
Explanation: "bb" is the only subsequence of length 2 that has the letter "b" appear at least 2 times.

Note:

1 <= repetition <= k <= s.length <= 5 * 10^4
s consists of lowercase English letters.
letter is a lowercase English letter, and appears in s at least repetition times.

Разобрать

Согласно смыслу вопроса, дана строка s, целое число k, буква letter и целое число повторений. Возвращает лексикографически наименьшую подпоследовательность s длины k, в которой буква встречается как минимум раз. В этом вопросе есть три ключевых момента: первый — возвращаемая подпоследовательность длины k, второй — она должна содержать буквенные буквы, третий — результирующая строка должна содержать повторяющиеся буквы, четвертый — убедиться, что полученная подпоследовательность Результат лексикографически наименьший. На самом деле, когда мы видим такого рода проблемы, мы можем в основном судить, что мы используем идею монотонного стека для решения проблемы и поддерживаем монотонный стек стека с возрастающим лексикографическим порядком, но ограничений больше, и нам нужно для обеспечения трех требований, упомянутых выше.

отвечать

class Solution(object):
    def smallestSubsequence(self, s, k, letter, repetition):
        c0 = len(s) - k   # 最多删除字符个数
        c1 = s.count(letter) - repetition # 最多删除的 letter 个数
        stack = []
        c2 = 0 # 统计删除了几个字符
        c3 = 0 # 统计删除了几个 letter
        for c in s:
            while stack and stack[-1]>c and c2<c0 and (stack[-1]!=letter or (stack[-1]==letter and c3<c1)):
                if stack[-1]==letter:
                    c3 += 1
                c2 += 1
                stack.pop()
            stack.append(c)
        result = ''
        for i in range(len(stack)-1, -1, -1):
            if c2==c0 or (stack[i]==letter and c1==c3):
                result += stack[i]
            else:
                c2 += 1
                if stack[i] == letter:
                    c3 += 1
        return result[::-1]

результат операции

Runtime: 2736 ms, faster than 6.67% of Python online submissions for Smallest K-Length Subsequence With Occurrences of a Letter.
Memory Usage: 16.6 MB, less than 6.67% of Python online submissions for Smallest K-Length Subsequence With Occurrences of a Letter.

Ссылка на оригинальное название:Lee TCO's.com/problems/what...

Ваша поддержка - моя самая большая мотивация

Категории