[LeetCode 2014] Longest Subsequence Repeated k Times

문제 바로가기

Description

---

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 "**b**a**bab**c**ba**".

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 <= k <= 2000
• 2 <= n < min(2001, k * 8)
• s consists of lowercase English letters.

Hint

---

Hint 1

  The length of the longest subsequence does not exceed n/k. Do you know why?
	

Hint 2

  Find the characters that could be included in the potential answer. A character occurring more than or equal to k times can be used in the answer up to (count of the character / k) times.
	

Hint 3

  Try all possible candidates in reverse lexicographic order, and check the string for the subsequence condition.
	

Code

---

내 제출

---

class Solution {
    private char[] s;

    public String longestSubsequenceRepeatedK(String s, int k) {
        this.s = s.toCharArray();
        int[] cnt = new int[26];
        for (char c : this.s) {
            cnt[c - 'a']++;
        }

        List<Character> cs = new ArrayList<>();
        for (char c = 'a'; c <= 'z'; ++c) {
            if (cnt[c - 'a'] >= k) {
                cs.add(c);
            }
        }
        Deque<String> q = new ArrayDeque<>();
        q.offer("");
        String ans = "";
        while (!q.isEmpty()) {
            String cur = q.poll();
            for (char c : cs) {
                String nxt = cur + c;
                if (check(nxt, k)) {
                    ans = nxt;
                    q.offer(nxt);
                }
            }
        }
        return ans;
    }

    private boolean check(String t, int k) {
        int i = 0;
        for (char c : s) {
            if (c == t.charAt(i)) {
                i++;
                if (i == t.length()) {
                    if (--k == 0) {
                        return true;
                    }
                    i = 0;
                }
            }
        }
        return false;
    }
}

Runtime	Memory
158 ms	45.2 MB

다른 풀이

---

class Solution {
    public String longestSubsequenceRepeatedK(String s, int k) {
        
        int n = s.length();

        int[] freq = new int[26];

        for(int i=0; i<n; i++){
            freq[s.charAt(i) - 'a']++;
        }

        List<Character> candidates = new ArrayList<>();

        for(int i=25; i>=0; i--){
            if(freq[i] >= k){
                candidates.add((char)(i + 'a'));
            }
        }

        Queue<String> queue = new LinkedList<>();

        for(char ch : candidates){
            queue.add(String.valueOf(ch));
        }

        String ans = "";

        while(!queue.isEmpty()){

            String curr = queue.poll();

            if(curr.length() > ans.length()){
                ans = curr;
            }

            for(char ch : candidates){
                String next = curr + ch;
                if(isRepeated(s, next, k)){
                    queue.add(next);
                }
            }
        }
        return ans;
    }

    public static boolean isRepeated(String s, String next, int k){

        int count = 0;

        int index = 0;

        for(char ch : s.toCharArray()){
            if(ch == next.charAt(index)){
                index++;
                if(index == next.length()){
                    index = 0;
                    count++;
                }
                if(count == k){
                    return true;
                }
            }
        }
        return false;
    }
}

Reference

---

• https://github.com/doocs/leetcode/blob/main/solution/2000-2099/2014.Longest%20Subsequence%20Repeated%20k%20Times/Solution.java