There is a key string S containing only letters, digits, and '-' (dashes). The N dashes divide the string into N+1 groups.

Given a number K, reformat the string so that each group contains exactly K characters. In particular, the first group must contain at most K characters, but at least 1 character. Separate adjacent groups with '-' (dashes), and convert all lowercase letters to uppercase.

Given a non-empty string S and a number K, format the string according to the rules above.

Example 1:

Input:S = "5F3Z-2e-9-w", K = 4
Output:"5F3Z-2E9W"
Explanation:The string S is split into two groups, each containing 4 characters;
     note that the two extra dashes must be removed.

Example 2:

Input:S = "2-5g-3-J", K = 2
Output:"2-5G-3J"
Explanation:The string S is split into 3 groups. According to the rules above, the first group may contain fewer than the specified number of characters, while every other group contains 2 characters.

Constraints:

1. S may be very long, so allocate memory as needed. K is a positive integer.
2. S contains only letters, digits (a-z, A-Z, 0-9), and the dash '-'.
3. S is non-empty.

Analysis

#

According to the problem, the dashes in the original string are not useful, so remove them while counting.

First calculate how many characters can be assigned to each group, represented by the variable parts. Then calculate how many characters belong in the first group, represented by remains. If the valid character count is divisible by K, the first group contains K characters; otherwise, it contains fewer than K characters, namely the number of valid characters divided by k.

Once these values have been calculated, fill the characters from the original string into the result. After filling remains characters, insert a dash and reset remains to K, because every subsequent group contains K characters.

Rust Code

#

# struct Solution;
impl Solution {
    pub fn license_key_formatting(s: String, k: i32) -> String {
        let k = k as usize;
        let n = s.len();
        let count = s.chars().fold(0, |acc, x| acc + (x == '-') as usize);
        let valid = n - count;
        let parts = valid / k + (valid % k > 0) as usize;
        let mut remains = if valid % k == 0 {k} else {valid % k};
        let mut res = "".to_string();
        for ch in s.chars() {
            if ch == '-' {
                continue;
            }
            if remains == 0 {
                res.push('-');
                remains = k;
            }
            res.push(ch.to_ascii_uppercase());
            remains -= 1;
        }
        res
    }
}