Daily classic

Inscribed Wall in Prison — Tan Sitong (Qing)

Wangmen cast stop think zhang Jian, endure a moment to wait for Dugan.

I smile from the horizontal knife to the day, to stay two Kunlun gallbladder.

describe

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".
Copy the code

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.
Copy the code

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.
Copy the code

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.
Copy the code

parsing

Given a string s, an integer k, a letter letter, and an integer repetition. Return the lexicographical smallest sequence of s whose letter occurrence is at least repetition of length k. There are three key points in this question. The first is that the subsequence of length K must be returned, the second is that letter must be included, the third is that the result string must contain repetition letter, and the fourth is to ensure that the result is the smallest lexicographic order. In fact, when we see this kind of problem, we can basically determine the use of monotone stack idea to solve the problem, maintain a monotonic stack of increasing lexicographical order, but there are more restrictions, to ensure the three requirements mentioned before.

answer

class Solution(object): def smallestSubsequence(self, s, k, letter, repetition): C0 = len(s) -k # number of letters to be deleted c1 = s.mount (letter) -repetition # Number of letters to be deleted stack = [] c2 = 0 # 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]Copy the code

The results

Runtime: 2736 ms, Faster than 6.67% of Python online submissions for longer k-length Subsequence With opportunities of a letter.memory Usage: Careers in the Python online submissions With opportunities of a Letter.Copy the code

Original link: leetcode.com/problems/sm…

Your support is my biggest motivation