LC1689: Partitioning Into Minimum Number Of Deci-Binary Numbers

Date: 2026-03-01
Difficulty: MEDIUM
Attempts: 1
Solution link: https://leetcode.com/submissions/detail/1934556803/
Question link: https://leetcode.com/problems/minimum-swaps-to-arrange-a-binary-grid

Also posted on leetcode: https://leetcode.com/problems/partitioning-into-minimum-number-of-deci-binary-numbers/solutions/7617169/java-solution-plus-explaination-plus-ret-zatl/

Intuition

You need to find the biggest number in the string.

There’s no requirement that the Deci-Binary numbers must have the same length, so your answer can be like this:

  27346209830709182346
# --------------------
1 11111101110101111111
2 11111101110101011111
3  1111001110101010111
4  1011001100101010011
5  1001001100101010001 
6  1001001100101010001
7  1000001100101010000
8        1100001010000
9        1000001000000

The problem become how many 1 it takes to construct the biggest digit in the string, basically just find the biggest digit in the string.

Approach

Find the biggest digit in the string.

You can just use Math.max, but here I wanna play with ASCII numbers a bit.

Complexity

Time complexity: $O(n)$

Space complexity: $O(1)$

Code

class Solution {
    public int minPartitions(String n) {
        char largest = 48;
        for (char c : n.toCharArray()) {
            if (c > largest) {
                if (c == 57) {
                    return 9;
                }
                largest = c;
            }
        }
        return largest - 48;
    }
}