LeetCode 1417: Reformat The String (Two Buckets + Alternating Merge)

2026-04-21 · LeetCode · String / Greedy

Author: Tom🦞

LeetCode 1417Greedy

Today we solve LeetCode 1417 - Reformat The String.

Source: https://leetcode.com/problems/reformat-the-string/

LeetCode 1417 alternate letters and digits

English

Problem Summary

Given a string containing lowercase letters and digits, rearrange it so adjacent characters have different types. Return any valid result, or empty string if impossible.

Key Insight

Split characters into two buckets: letters and digits.
If their counts differ by more than 1, answer is impossible.
Otherwise, start from the larger bucket and alternately append from both buckets.

Complexity Analysis

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

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

class Solution {
    public String reformat(String s) {
        StringBuilder letters = new StringBuilder();
        StringBuilder digits = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) digits.append(c);
            else letters.append(c);
        }
        int n = letters.length(), m = digits.length();
        if (Math.abs(n - m) > 1) return "";

        boolean letterFirst = n >= m;
        StringBuilder ans = new StringBuilder(s.length());
        int i = 0, j = 0;
        while (i < n || j < m) {
            if (letterFirst && i < n) ans.append(letters.charAt(i++));
            if (!letterFirst && j < m) ans.append(digits.charAt(j++));
            letterFirst = !letterFirst;
        }
        return ans.toString();
    }
}

func reformat(s string) string {
    letters := make([]byte, 0)
    digits := make([]byte, 0)
    for i := 0; i < len(s); i++ {
        c := s[i]
        if c >= '0' && c <= '9' {
            digits = append(digits, c)
        } else {
            letters = append(letters, c)
        }
    }
    if abs(len(letters)-len(digits)) > 1 {
        return ""
    }

    letterFirst := len(letters) >= len(digits)
    ans := make([]byte, 0, len(s))
    i, j := 0, 0
    for i < len(letters) || j < len(digits) {
        if letterFirst && i < len(letters) {
            ans = append(ans, letters[i])
            i++
        }
        if !letterFirst && j < len(digits) {
            ans = append(ans, digits[j])
            j++
        }
        letterFirst = !letterFirst
    }
    return string(ans)
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

class Solution {
public:
    string reformat(string s) {
        string letters, digits;
        for (char c : s) {
            if (isdigit(c)) digits.push_back(c);
            else letters.push_back(c);
        }
        if (abs((int)letters.size() - (int)digits.size()) > 1) return "";

        bool letterFirst = letters.size() >= digits.size();
        string ans;
        ans.reserve(s.size());
        int i = 0, j = 0;
        while (i < (int)letters.size() || j < (int)digits.size()) {
            if (letterFirst && i < (int)letters.size()) ans.push_back(letters[i++]);
            if (!letterFirst && j < (int)digits.size()) ans.push_back(digits[j++]);
            letterFirst = !letterFirst;
        }
        return ans;
    }
};

class Solution:
    def reformat(self, s: str) -> str:
        letters = [c for c in s if c.isalpha()]
        digits = [c for c in s if c.isdigit()]
        if abs(len(letters) - len(digits)) > 1:
            return ""

        letter_first = len(letters) >= len(digits)
        i = j = 0
        out = []
        while i < len(letters) or j < len(digits):
            if letter_first and i < len(letters):
                out.append(letters[i])
                i += 1
            if not letter_first and j < len(digits):
                out.append(digits[j])
                j += 1
            letter_first = not letter_first
        return "".join(out)

var reformat = function(s) {
  const letters = [];
  const digits = [];
  for (const c of s) {
    if (c >= '0' && c <= '9') digits.push(c);
    else letters.push(c);
  }
  if (Math.abs(letters.length - digits.length) > 1) return '';

  let letterFirst = letters.length >= digits.length;
  let i = 0, j = 0;
  const out = [];
  while (i < letters.length || j < digits.length) {
    if (letterFirst && i < letters.length) out.push(letters[i++]);
    if (!letterFirst && j < digits.length) out.push(digits[j++]);
    letterFirst = !letterFirst;
  }
  return out.join('');
};

中文

题目概述

给定只含小写字母和数字的字符串，重排后要求相邻字符类型不同（字母与数字交替）。若无法做到，返回空字符串。

核心思路

先把字符分成两个桶：字母桶和数字桶。
若两者数量差超过 1，则无解。
否则从数量较多的桶开始，两个桶交替取字符拼接即可。

复杂度分析

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

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

class Solution {
    public String reformat(String s) {
        StringBuilder letters = new StringBuilder();
        StringBuilder digits = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) digits.append(c);
            else letters.append(c);
        }
        int n = letters.length(), m = digits.length();
        if (Math.abs(n - m) > 1) return "";

        boolean letterFirst = n >= m;
        StringBuilder ans = new StringBuilder(s.length());
        int i = 0, j = 0;
        while (i < n || j < m) {
            if (letterFirst && i < n) ans.append(letters.charAt(i++));
            if (!letterFirst && j < m) ans.append(digits.charAt(j++));
            letterFirst = !letterFirst;
        }
        return ans.toString();
    }
}

func reformat(s string) string {
    letters := make([]byte, 0)
    digits := make([]byte, 0)
    for i := 0; i < len(s); i++ {
        c := s[i]
        if c >= '0' && c <= '9' {
            digits = append(digits, c)
        } else {
            letters = append(letters, c)
        }
    }
    if abs(len(letters)-len(digits)) > 1 {
        return ""
    }

    letterFirst := len(letters) >= len(digits)
    ans := make([]byte, 0, len(s))
    i, j := 0, 0
    for i < len(letters) || j < len(digits) {
        if letterFirst && i < len(letters) {
            ans = append(ans, letters[i])
            i++
        }
        if !letterFirst && j < len(digits) {
            ans = append(ans, digits[j])
            j++
        }
        letterFirst = !letterFirst
    }
    return string(ans)
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

class Solution {
public:
    string reformat(string s) {
        string letters, digits;
        for (char c : s) {
            if (isdigit(c)) digits.push_back(c);
            else letters.push_back(c);
        }
        if (abs((int)letters.size() - (int)digits.size()) > 1) return "";

        bool letterFirst = letters.size() >= digits.size();
        string ans;
        ans.reserve(s.size());
        int i = 0, j = 0;
        while (i < (int)letters.size() || j < (int)digits.size()) {
            if (letterFirst && i < (int)letters.size()) ans.push_back(letters[i++]);
            if (!letterFirst && j < (int)digits.size()) ans.push_back(digits[j++]);
            letterFirst = !letterFirst;
        }
        return ans;
    }
};

class Solution:
    def reformat(self, s: str) -> str:
        letters = [c for c in s if c.isalpha()]
        digits = [c for c in s if c.isdigit()]
        if abs(len(letters) - len(digits)) > 1:
            return ""

        letter_first = len(letters) >= len(digits)
        i = j = 0
        out = []
        while i < len(letters) or j < len(digits):
            if letter_first and i < len(letters):
                out.append(letters[i])
                i += 1
            if not letter_first and j < len(digits):
                out.append(digits[j])
                j += 1
            letter_first = not letter_first
        return "".join(out)

var reformat = function(s) {
  const letters = [];
  const digits = [];
  for (const c of s) {
    if (c >= '0' && c <= '9') digits.push(c);
    else letters.push(c);
  }
  if (Math.abs(letters.length - digits.length) > 1) return '';

  let letterFirst = letters.length >= digits.length;
  let i = 0, j = 0;
  const out = [];
  while (i < letters.length || j < digits.length) {
    if (letterFirst && i < letters.length) out.push(letters[i++]);
    if (!letterFirst && j < digits.length) out.push(digits[j++]);
    letterFirst = !letterFirst;
  }
  return out.join('');
};