< Back





2182. Construct String With Repeat Limit

Not a super popular question, but we'll knock it out anyways. This one's hard to reason about because
of the requirement of the string to be lexicographically greater, which is an annoying way of saying
that between two strings, for any position, the greater string will have a character that is
ordinally greater than the other string's character at that position. For the correct answer, we need
to position the characters within the existing string such that characters in the new string don't
repeat more than repeatLimit times.

To solve this, we acquire the frequency of each character in the string, and push them onto a max
heap. Our lexicographically greatest character will be at the top of the heap, and we'll iterate on
this heap until it's empty.

We pop the lexicographically greatest character from the heap. If it's frequency is less than or
equal to the repeatLimit, we append it to the answer array. Else, we append repeatLimit instances of
this character to the answer array. If no remaining characters are on the heap, we terminate. Else,
we pop again from the heap to retrieve the next lexicographically greatest character, and append
one instance of the next character to the answer array.

If the next character's frequency is greater than 1, we push it back onto the heap, less one
instance. Finally, we push the original character back onto the heap, less repeatLimit instances.

The solution is as follows:


  from heapq import heapify, heappop, heappush

  class Solution:
      def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
          heap = [(-ord(char), count) for char, count in Counter(s).items()]
          heapq.heapify(heap)
          ans = []

          while heap:
              char, count = heapq.heappop(heap)

              if count <= repeatLimit:
                  ans += [chr(-char)] * count
              else:
                  ans += [chr(-char)] * repeatLimit

                  if not heap:
                      break

                  nchar, ncount = heapq.heappop(heap)
                  ans += chr(-nchar)

                  if ncount > 1:
                      heapq.heappush(heap, (nchar, ncount - 1))

                  heapq.heappush(heap, (char, count - repeatLimit))

          return ''.join(ans)


_ Time Complexity:

  O(n * log(n)) - We iterate through the string to count characters, and we push or pop each
  character onto the heap in log(n) time.

_ Space Complexity:

  O(n) - We use n space to store the heap, and the answer array will be at most n characters long.