Skip to content

2182. Construct String With Repeat Limit 👍

  • Time: $O(|\texttt{s}|)$
  • Space: $O(|\texttt{s}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
 public:
  string repeatLimitedString(string s, int repeatLimit) {
    string ans;
    vector<int> count(26);

    for (const char c : s)
      ++count[c - 'a'];

    while (true) {
      const bool addOne = !ans.empty() && shouldAddOne(ans, count);
      const int i = getLargestChar(ans, count);
      if (i == -1)
        break;
      const int repeats = addOne ? 1 : min(count[i], repeatLimit);
      ans += string(repeats, 'a' + i);
      count[i] -= repeats;
    }

    return ans;
  }

 private:
  bool shouldAddOne(const string& ans, const vector<int>& count) {
    for (int i = 25; i >= 0; --i)
      if (count[i])
        return ans.back() == 'a' + i;
    return false;
  }

  int getLargestChar(const string& ans, const vector<int>& count) {
    for (int i = 25; i >= 0; --i)
      if (count[i] && (ans.empty() || ans.back() != 'a' + i))
        return i;
    return -1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
  public String repeatLimitedString(String s, int repeatLimit) {
    StringBuilder sb = new StringBuilder();
    int[] count = new int[26];

    for (final char c : s.toCharArray())
      ++count[c - 'a'];

    while (true) {
      final boolean addOne = !sb.isEmpty() && shouldAddOne(sb, count);
      final int i = getLargestChar(sb, count);
      if (i == -1)
        break;
      final int repeats = addOne ? 1 : Math.min(count[i], repeatLimit);
      sb.append(String.valueOf((char) ('a' + i)).repeat(repeats));
      count[i] -= repeats;
    }

    return sb.toString();
  }

  private boolean shouldAddOne(StringBuilder sb, int[] count) {
    for (int i = 25; i >= 0; --i)
      if (count[i] > 0)
        return sb.charAt(sb.length() - 1) == 'a' + i;
    return false;
  }

  private int getLargestChar(StringBuilder sb, int[] count) {
    for (int i = 25; i >= 0; --i)
      if (count[i] > 0 && (sb.isEmpty() || sb.charAt(sb.length() - 1) != 'a' + i))
        return i;
    return -1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
  def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
    ans = ''
    count = collections.Counter(s)

    while True:
      addOne = ans and self._shouldAddOne(ans, count)
      c = self._getLargestChar(ans, count)
      if c == ' ':
        break
      repeats = 1 if addOne else min(count[c], repeatLimit)
      ans += c * repeats
      count[c] -= repeats

    return ans

  def _shouldAddOne(self, ans: str, count: collections.Counter) -> bool:
    for c in reversed(string.ascii_lowercase):
      if count[c]:
        return ans[-1] == c
    return False

  def _getLargestChar(self, ans: str, count: collections.Counter) -> int:
    for c in reversed(string.ascii_lowercase):
      if count[c] and (not ans or ans[-1] != c):
        return c
    return ' '