Smallest K-Length Subsequence With Occurrences of a Letter

// Accepted solution for LeetCode #2030: Smallest K-Length Subsequence With Occurrences of a Letter
class Solution {
  public String smallestSubsequence(String s, int k, char letter, int repetition) {
    StringBuilder sb = new StringBuilder();
    Deque<Character> stack = new ArrayDeque<>();
    int required = repetition;
    int nLetters = (int) s.chars().filter(c -> c == letter).count();

    for (int i = 0; i < s.length(); ++i) {
      final char c = s.charAt(i);
      while (!stack.isEmpty() && stack.peek() > c && stack.size() + s.length() - i - 1 >= k &&
             (stack.peek() != letter || nLetters > required))
        if (stack.pop() == letter)
          ++required;
      if (stack.size() < k)
        if (c == letter) {
          stack.push(c);
          --required;
        } else if (k - stack.size() > required) {
          stack.push(c);
        }
      if (c == letter)
        --nLetters;
    }

    for (final char c : stack)
      sb.append(c);

    return sb.reverse().toString();
  }
}

// Accepted solution for LeetCode #2030: Smallest K-Length Subsequence With Occurrences of a Letter
// Auto-generated Go example from java.
func exampleSolution() {
}
// Reference (java):
// // Accepted solution for LeetCode #2030: Smallest K-Length Subsequence With Occurrences of a Letter
// class Solution {
//   public String smallestSubsequence(String s, int k, char letter, int repetition) {
//     StringBuilder sb = new StringBuilder();
//     Deque<Character> stack = new ArrayDeque<>();
//     int required = repetition;
//     int nLetters = (int) s.chars().filter(c -> c == letter).count();
// 
//     for (int i = 0; i < s.length(); ++i) {
//       final char c = s.charAt(i);
//       while (!stack.isEmpty() && stack.peek() > c && stack.size() + s.length() - i - 1 >= k &&
//              (stack.peek() != letter || nLetters > required))
//         if (stack.pop() == letter)
//           ++required;
//       if (stack.size() < k)
//         if (c == letter) {
//           stack.push(c);
//           --required;
//         } else if (k - stack.size() > required) {
//           stack.push(c);
//         }
//       if (c == letter)
//         --nLetters;
//     }
// 
//     for (final char c : stack)
//       sb.append(c);
// 
//     return sb.reverse().toString();
//   }
// }

# Accepted solution for LeetCode #2030: Smallest K-Length Subsequence With Occurrences of a Letter
class Solution:
  def smallestSubsequence(
      self,
      s: str,
      k: int,
      letter: str,
      repetition: int,
  ) -> str:
    stack = []  # running string
    required = repetition
    nLetters = s.count(letter)

    for i, c in enumerate(s):
      # Make sure the length is sufficient:
      # Len(stack) := the length of running string
      # Len(s) - i := the length of remain chars
      # -1 := we're going to pop a char
      while (stack and stack[-1] > c
              and len(stack) + len(s) - i - 1 >= k
              and (stack[-1] != letter or nLetters > required)):
        if stack.pop() == letter:
          required += 1
      if len(stack) < k:
        if c == letter:
          stack.append(c)
          required -= 1
        elif k - len(stack) > required:
          stack.append(c)
      if c == letter:
        nLetters -= 1

    return ''.join(stack)

// Accepted solution for LeetCode #2030: Smallest K-Length Subsequence With Occurrences of a Letter
/**
 * [2030] Smallest K-Length Subsequence With Occurrences of a Letter
 *
 * 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 "<u>lee</u>t")
 * - "let" (from "<u>le</u>e<u>t</u>")
 * - "let" (from "<u>l</u>e<u>et</u>")
 * - "eet" (from "l<u>eet</u>")
 * The lexicographically smallest subsequence among them is "eet".
 *
 * Example 2:
 * <img alt="example-2" src="https://assets.leetcode.com/uploads/2021/09/13/smallest-k-length-subsequence.png" style="width: 339px; height: 67px;" />
 * 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.
 *
 *  
 * Constraints:
 *
 * 	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.
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/smallest-k-length-subsequence-with-occurrences-of-a-letter/
// discuss: https://leetcode.com/problems/smallest-k-length-subsequence-with-occurrences-of-a-letter/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn smallest_subsequence(s: String, k: i32, letter: char, repetition: i32) -> String {
        String::new()
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[ignore]
    fn test_2030_example_1() {
        let s = "leet".to_string();
        let k = 3;
        let letter = 'e';
        let repetition = 1;

        let result = "eet".to_string();

        assert_eq!(
            Solution::smallest_subsequence(s, k, letter, repetition),
            result
        );
    }

    #[test]
    #[ignore]
    fn test_2030_example_2() {
        let s = "leetcode".to_string();
        let k = 4;
        let letter = 'e';
        let repetition = 2;

        let result = "ecde".to_string();

        assert_eq!(
            Solution::smallest_subsequence(s, k, letter, repetition),
            result
        );
    }

    #[test]
    #[ignore]
    fn test_2030_example_3() {
        let s = "bb".to_string();
        let k = 2;
        let letter = 'b';
        let repetition = 2;

        let result = "bb".to_string();

        assert_eq!(
            Solution::smallest_subsequence(s, k, letter, repetition),
            result
        );
    }
}

// Accepted solution for LeetCode #2030: Smallest K-Length Subsequence With Occurrences of a Letter
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #2030: Smallest K-Length Subsequence With Occurrences of a Letter
// class Solution {
//   public String smallestSubsequence(String s, int k, char letter, int repetition) {
//     StringBuilder sb = new StringBuilder();
//     Deque<Character> stack = new ArrayDeque<>();
//     int required = repetition;
//     int nLetters = (int) s.chars().filter(c -> c == letter).count();
// 
//     for (int i = 0; i < s.length(); ++i) {
//       final char c = s.charAt(i);
//       while (!stack.isEmpty() && stack.peek() > c && stack.size() + s.length() - i - 1 >= k &&
//              (stack.peek() != letter || nLetters > required))
//         if (stack.pop() == letter)
//           ++required;
//       if (stack.size() < k)
//         if (c == letter) {
//           stack.push(c);
//           --required;
//         } else if (k - stack.size() > required) {
//           stack.push(c);
//         }
//       if (c == letter)
//         --nLetters;
//     }
// 
//     for (final char c : stack)
//       sb.append(c);
// 
//     return sb.reverse().toString();
//   }
// }