LeetCode Problem 2138

Difficulty: 🟢 Easy
Topics: String, Simulation

Solution

LeetCode 2138 - Divide a String Into Groups of Size k

Problem Understanding

The problem asks us to split a string into consecutive groups, where every group must contain exactly k characters.

We process the string from left to right. The first k characters form the first group, the next k characters form the second group, and so on. Every character from the original string must belong to exactly one group.

The only complication happens with the final group. If the number of remaining characters is smaller than k, we must append the character fill enough times to make the last group reach size k.

The input consists of:

• s, the original string
• k, the required size of every group
• fill, a single character used for padding the last group if necessary

The output is an array of strings, where each string has length exactly k.

For example, if:

s = "abcdefghij"
k = 3
fill = "x"

we split the string like this:

abc | def | ghi | j

The last piece only contains one character, so we append two 'x' characters:

jxx

The final answer becomes:

["abc", "def", "ghi", "jxx"]

The constraints are very small:

• s.length <= 100
• k <= 100

This tells us performance is not a major concern. Even a straightforward simulation will easily fit within limits. However, we still want a clean and efficient implementation.

There are several important edge cases to keep in mind:

• The string length may already be divisible by k, meaning no padding is needed.
• The string may contain fewer than k characters total.
• k may equal 1, meaning every character becomes its own group.
• The final group may require multiple fill characters.

A correct solution must handle all of these situations consistently.

Approaches

Brute Force Approach

A brute force solution could repeatedly build each group character by character.

We could iterate through the string using an index, manually append up to k characters into a temporary string, and if we run out of characters before reaching size k, continue appending the fill character until the group reaches the required size.

This approach is correct because it explicitly simulates the grouping process exactly as described in the problem statement.

However, the implementation becomes unnecessarily verbose. We end up managing many conditions manually:

• Tracking the current group size
• Checking whether we reached the end of the string
• Appending fill characters separately

Although the constraints are small, this method is more complicated than necessary.

Optimal Approach

The key observation is that strings can already be sliced directly into chunks of size k.

Instead of building groups character by character, we can iterate through the string in steps of size k:

• Extract a substring from index i to i + k
• If the substring length is smaller than k, append enough fill characters
• Add the completed group to the answer list

This approach is simpler, cleaner, and naturally matches the structure of the problem.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Manually builds each group character by character
Optimal	O(n)	O(n)	Uses substring slicing and simple padding logic

Algorithm Walkthrough

Optimal Algorithm

1. Initialize an empty result list that will store all groups.
2. Iterate through the string using a step size of k.

This ensures that each iteration processes exactly one group. 3. For each starting index i, extract the substring:

s[i:i+k]

This gives the current group candidate. 4. Check whether the extracted substring has length smaller than k.

This only happens for the final group when the string length is not divisible by k. 5. If the group is too short, calculate how many characters are missing:

k - len(group)

6. Append the fill character that many times.
7. Add the completed group to the result list.
8. After processing all groups, return the result list.

Why it works

The algorithm processes the string in non-overlapping chunks of size k. Every character belongs to exactly one chunk because the loop advances by k each iteration. If the final chunk is incomplete, padding ensures its size becomes exactly k. Therefore, the produced groups satisfy all conditions in the problem statement.

Python Solution

from typing import List

class Solution:
    def divideString(self, s: str, k: int, fill: str) -> List[str]:
        groups = []

        for i in range(0, len(s), k):
            group = s[i:i + k]

            if len(group) < k:
                group += fill * (k - len(group))

            groups.append(group)

        return groups

The implementation begins by creating an empty list called groups, which stores the final answer.

The loop iterates through the string using:

range(0, len(s), k)

The step size k guarantees that each iteration starts at the beginning of a new group.

The expression:

s[i:i + k]

extracts up to k characters from the current position.

If the extracted substring is shorter than k, the code appends enough copies of fill to complete the group.

Finally, each completed group is added to the result list, and the list is returned after all groups are processed.

Go Solution

func divideString(s string, k int, fill byte) []string {
    result := []string{}

    for i := 0; i < len(s); i += k {
        end := i + k

        if end > len(s) {
            end = len(s)
        }

        group := s[i:end]

        for len(group) < k {
            group += string(fill)
        }

        result = append(result, group)
    }

    return result
}

The Go implementation follows the same logic as the Python solution, but there are a few language-specific differences.

Go does not support Python-style slicing beyond array bounds, so we explicitly clamp the ending index using:

if end > len(s) {
    end = len(s)
}

The fill parameter is a byte, so we convert it into a string before concatenation:

string(fill)

The result is stored in a slice of strings, which dynamically grows as groups are appended.

Worked Examples

Example 1

Input:
s = "abcdefghi"
k = 3
fill = "x"

Iteration Trace

Iteration	i	Extracted Group	Needs Padding	Final Group	Result
1	0	"abc"	No	"abc"	["abc"]
2	3	"def"	No	"def"	["abc", "def"]
3	6	"ghi"	No	"ghi"	["abc", "def", "ghi"]

Final output:

["abc","def","ghi"]

Example 2

Input:
s = "abcdefghij"
k = 3
fill = "x"

Iteration Trace

Iteration	i	Extracted Group	Needs Padding	Final Group	Result
1	0	"abc"	No	"abc"	["abc"]
2	3	"def"	No	"def"	["abc", "def"]
3	6	"ghi"	No	"ghi"	["abc", "def", "ghi"]
4	9	"j"	Yes, add 2 x's	"jxx"	["abc", "def", "ghi", "jxx"]

Final output:

["abc","def","ghi","jxx"]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every character is processed at most once
Space	O(n)	The output groups together contain all original characters plus possible padding

The algorithm scans the string in chunks of size k. Since every character belongs to exactly one group, the total amount of work grows linearly with the length of the string. The output itself also requires linear space because all groups must be stored and returned.

Test Cases

from typing import List

class Solution:
    def divideString(self, s: str, k: int, fill: str) -> List[str]:
        groups = []

        for i in range(0, len(s), k):
            group = s[i:i + k]

            if len(group) < k:
                group += fill * (k - len(group))

            groups.append(group)

        return groups

sol = Solution()

assert sol.divideString("abcdefghi", 3, "x") == ["abc", "def", "ghi"]  # exact division
assert sol.divideString("abcdefghij", 3, "x") == ["abc", "def", "ghi", "jxx"]  # padding needed
assert sol.divideString("a", 3, "z") == ["azz"]  # single character input
assert sol.divideString("abcd", 2, "x") == ["ab", "cd"]  # no padding with even split
assert sol.divideString("abcde", 2, "y") == ["ab", "cd", "ey"]  # one fill character
assert sol.divideString("abc", 1, "x") == ["a", "b", "c"]  # k equals 1
assert sol.divideString("hello", 10, "q") == ["helloqqqqq"]  # k larger than string length
assert sol.divideString("zzzz", 3, "a") == ["zzz", "zaa"]  # repeated characters
assert sol.divideString("p", 1, "x") == ["p"]  # smallest valid k

Test	Why
"abcdefghi", k=3	Verifies exact division without padding
"abcdefghij", k=3	Verifies padding logic
"a", k=3	Tests very short input
"abcd", k=2	Tests evenly divisible string
"abcde", k=2	Tests single padding character
"abc", k=1	Verifies smallest group size
"hello", k=10	Tests k larger than string length
"zzzz", k=3	Tests repeated characters
"p", k=1	Tests smallest valid overall case

Edge Cases

String Length Already Divisible by k

One common source of bugs is accidentally adding padding even when the final group already contains exactly k characters.

For example:

s = "abcdef"
k = 3

The groups should simply be:

["abc", "def"]

The implementation correctly avoids padding because it only appends fill characters when:

len(group) < k

String Shorter Than k

Another important edge case occurs when the entire string is smaller than the required group size.

For example:

s = "a"
k = 4
fill = "x"

The correct result is:

["axxx"]

The implementation handles this naturally because the loop still extracts one substring, then pads it until its length reaches k.

k Equals 1

When k = 1, every character forms its own group.

For example:

s = "abc"
k = 1

The output becomes:

["a", "b", "c"]

This case can expose bugs in implementations that incorrectly assume groups contain multiple characters. The step size in the loop becomes 1, so every character is processed individually, which works correctly.

Multiple Fill Characters Needed

The final group may require more than one fill character.

For example:

s = "abcde"
k = 4
fill = "z"

The last group starts as:

"e"

and must become:

"ezzz"

The implementation computes the exact number of missing characters using:

k - len(group)

which guarantees the correct amount of padding is added.