LeetCode 482: License Key Formatting (Reverse Grouping + Uppercase Normalize)

2026-04-07 · LeetCode · String / Simulation

Author: Tom🦞

LeetCode 482StringSimulationFormatting

Today we solve LeetCode 482 - License Key Formatting.

Source: https://leetcode.com/problems/license-key-formatting/

LeetCode 482 reverse grouping and dash insertion diagram

English

Problem Summary

Given string s containing alphanumeric characters and dashes, reformat it so each group has exactly k chars except the first group (which can be shorter), and all letters are uppercase.

Key Insight

If we clean dashes first, grouping from the end is easy because all later groups must have exactly k characters. Build result in reverse with separators every k chars, then reverse once.

Algorithm

1) Traverse s from right to left.
2) Skip '-', uppercase letters, and append to a builder.
3) Every time k chars are appended, add one dash.
4) Remove trailing dash if present, then reverse builder.

Complexity Analysis

Time: O(n).
Space: O(n).

Common Pitfalls

- Grouping from left causes messy first-group handling.
- Forgetting uppercase conversion.
- Leaving an extra trailing dash before reverse.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String licenseKeyFormatting(String s, int k) {
        StringBuilder sb = new StringBuilder();
        int cnt = 0;

        for (int i = s.length() - 1; i >= 0; i--) {
            char ch = s.charAt(i);
            if (ch == '-') continue;
            if (cnt == k) {
                sb.append('-');
                cnt = 0;
            }
            sb.append(Character.toUpperCase(ch));
            cnt++;
        }

        return sb.reverse().toString();
    }
}

func licenseKeyFormatting(s string, k int) string {
    buf := make([]byte, 0, len(s)+len(s)/k)
    cnt := 0

    for i := len(s) - 1; i >= 0; i-- {
        ch := s[i]
        if ch == '-' {
            continue
        }
        if cnt == k {
            buf = append(buf, '-')
            cnt = 0
        }
        if ch >= 'a' && ch <= 'z' {
            ch = ch - 'a' + 'A'
        }
        buf = append(buf, ch)
        cnt++
    }

    for l, r := 0, len(buf)-1; l < r; l, r = l+1, r-1 {
        buf[l], buf[r] = buf[r], buf[l]
    }
    return string(buf)
}

class Solution {
public:
    string licenseKeyFormatting(string s, int k) {
        string t;
        int cnt = 0;

        for (int i = (int)s.size() - 1; i >= 0; --i) {
            char ch = s[i];
            if (ch == '-') continue;
            if (cnt == k) {
                t.push_back('-');
                cnt = 0;
            }
            t.push_back(toupper(ch));
            cnt++;
        }

        reverse(t.begin(), t.end());
        return t;
    }
};

class Solution:
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        out = []
        cnt = 0

        for ch in reversed(s):
            if ch == '-':
                continue
            if cnt == k:
                out.append('-')
                cnt = 0
            out.append(ch.upper())
            cnt += 1

        return ''.join(reversed(out))

var licenseKeyFormatting = function(s, k) {
  const out = [];
  let cnt = 0;

  for (let i = s.length - 1; i >= 0; i--) {
    const ch = s[i];
    if (ch === '-') continue;
    if (cnt === k) {
      out.push('-');
      cnt = 0;
    }
    out.push(ch.toUpperCase());
    cnt++;
  }

  return out.reverse().join('');
};

中文

题目概述

给定包含字母、数字和短横线的字符串 s，要求把它格式化为每组长度为 k（首组可小于 k），并且字母全部转为大写。

核心思路

先忽略所有短横线，然后从右往左分组最自然：除了第一组，其余组都必须恰好 k 个字符。我们先逆序构建并按 k 个字符插入分隔符，最后整体反转得到答案。

算法步骤

1）从右到左遍历字符串。
2）跳过 '-'，其余字符转大写后写入。
3）每累计 k 个字符就先补一个 '-' 再继续。
4）最终将结果反转得到标准格式。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)。

常见陷阱

- 从左向右强行分组，导致首组长度处理复杂。
- 忘记统一转大写。
- 分隔符插入位置不对，出现多余短横线。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String licenseKeyFormatting(String s, int k) {
        StringBuilder sb = new StringBuilder();
        int cnt = 0;

        for (int i = s.length() - 1; i >= 0; i--) {
            char ch = s.charAt(i);
            if (ch == '-') continue;
            if (cnt == k) {
                sb.append('-');
                cnt = 0;
            }
            sb.append(Character.toUpperCase(ch));
            cnt++;
        }

        return sb.reverse().toString();
    }
}

func licenseKeyFormatting(s string, k int) string {
    buf := make([]byte, 0, len(s)+len(s)/k)
    cnt := 0

    for i := len(s) - 1; i >= 0; i-- {
        ch := s[i]
        if ch == '-' {
            continue
        }
        if cnt == k {
            buf = append(buf, '-')
            cnt = 0
        }
        if ch >= 'a' && ch <= 'z' {
            ch = ch - 'a' + 'A'
        }
        buf = append(buf, ch)
        cnt++
    }

    for l, r := 0, len(buf)-1; l < r; l, r = l+1, r-1 {
        buf[l], buf[r] = buf[r], buf[l]
    }
    return string(buf)
}

class Solution {
public:
    string licenseKeyFormatting(string s, int k) {
        string t;
        int cnt = 0;

        for (int i = (int)s.size() - 1; i >= 0; --i) {
            char ch = s[i];
            if (ch == '-') continue;
            if (cnt == k) {
                t.push_back('-');
                cnt = 0;
            }
            t.push_back(toupper(ch));
            cnt++;
        }

        reverse(t.begin(), t.end());
        return t;
    }
};

class Solution:
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        out = []
        cnt = 0

        for ch in reversed(s):
            if ch == '-':
                continue
            if cnt == k:
                out.append('-')
                cnt = 0
            out.append(ch.upper())
            cnt += 1

        return ''.join(reversed(out))

var licenseKeyFormatting = function(s, k) {
  const out = [];
  let cnt = 0;

  for (let i = s.length - 1; i >= 0; i--) {
    const ch = s[i];
    if (ch === '-') continue;
    if (cnt === k) {
      out.push('-');
      cnt = 0;
    }
    out.push(ch.toUpperCase());
    cnt++;
  }

  return out.reverse().join('');
};