**Solution with discussion** https://discuss.leetcode.com/topic/74985/python-solution-using-deque-detailed-explanation

**License Key Formatting** https://leetcode.com/problems/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:
q.appendleft("-")
q.appendleft(S[i].upper())
cnt = 1
else:
q.appendleft(S[i].upper())
cnt += 1
return "".join(q)
```