Python solution using deque - detailed explanation

  • 0

    Solution with discussion

    License Key Formatting

    Solution using a deque

    • Start from the last character and add items to top of deque
    • Inset delimiter wher cnt %K == 0. cnt includes just character count and not "-".
    • Invariant: cnt first reaches K and in next iteration we test for adding "-". This ensures we do not add un-necessarily add a "-" at start.
    • Beware of boundary condition - do not insert "-" without inserting any other character in the queue.
    from collections import deque
    class Solution(object):
        def licenseKeyFormatting(self, S, K):
            :type S: str
            :type K: int
            :rtype: str
            q, cnt = deque(), 0
            for i in range(len(S)-1,-1,-1):
                if S[i] != "-":
                    if cnt % K == 0 and cnt > 0:
                        cnt = 1
                        cnt += 1
            return "".join(q)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.