Today I have done leetcode's June LeetCoding Challenge with cpp.

June LeetCoding Challenge 27

Description

Longest Subsequence Repeated k Times

You are given a string s of length n, and an integer k. You are tasked to find the longest subsequence repeated k times in string s.

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 subsequence seq is repeated k times in the string s if seq * k is a subsequence of s, where seq * k represents a string constructed by concatenating seq k times.

For example, "bba" is repeated 2 times in the string "bababcba", because the string "bbabba", constructed by concatenating "bba" 2 times, is a subsequence of the string "bababcba".

Return the longest subsequence repeated k times in string s. If multiple such subsequences are found, return the lexicographically largest one. If there is no such subsequence, return an empty string.

Example 1:

Input: s = "letsleetcode", k = 2
Output: "let"
Explanation: There are two longest subsequences repeated 2 times: "let" and "ete".
"let" is the lexicographically largest one.

Example 2:

Input: s = "bb", k = 2
Output: "b"
Explanation: The longest subsequence repeated 2 times is "b".

Example 3:

Input: s = "ab", k = 2
Output: ""
Explanation: There is no subsequence repeated 2 times. Empty string is returned.

Constraints:

n == s.length
2 <= n, k <= 2000
2 <= n < k * 8
s consists of lowercase English letters.

Solution

class Solution {
  bool isValid(const string &s, const string &pattern, int k) {
    if(pattern.empty()) return true;
    int lenP = pattern.length();
    int pos = 0;
    for(auto c : s) {
      if(c != pattern[pos]) continue;
      pos += 1;
      if(pos == lenP) {
        k -= 1;
        pos = 0;
      }
    }
    return k < 1;
  }
  void solve(
    const string &s,
    string &answer,
    string &current,
    vector<int> count,
    int k
  ) {
    // cout << s << ' ' << answer << ' ' << current << endl;
    if(current.length() > answer.length() || (current.length() == answer.length() && current > answer)) answer = current;
    for(int i = 0; i < 26; ++i) {
      if(!count[i]) continue;
      count[i] -= 1;
      current.push_back(i + 'a');
      if(isValid(s, current, k)) solve(s, answer, current, count, k);
      current.pop_back();
      count[i] += 1;
    }
  }
public:
  string longestSubsequenceRepeatedK(string s, int k) {
    vector<int> count(26);
    for(auto c : s) {
      count[c - 'a'] += 1;
    }
    for(auto &cnt : count) {
      cnt /= k;
    }
    string answer;
    string tmp;
    solve(s, answer, tmp, count, k);
    return answer;
  }
};

// Accepted
// 313/313 cases passed (67 ms)
// Your runtime beats 97.83 % of cpp submissions
// Your memory usage beats 55.8 % of cpp submissions (14 MB)

2025-06-27 Daily Challenge

June LeetCoding Challenge 27

Description

Solution