Divide a String Into Groups of Size k

Difficulty: Easy | Acceptance: 77.10% | Paid: No Topics: String, Simulation

A string s can be partitioned into groups of size k using the following procedure:

The first group consists of the first k characters of s, the second group consists of the next k characters of s, and so on. A group can have less than k characters if there are less than k characters left in s.

The last group is filled with characters from fill to make it of size k. Note that a group consisting of only fill characters is valid.

Return an array of strings denoting the composition of every group in s.

• Examples
• Constraints
• Iterative Simulation
• Built-in Padding

Examples

Example 1

Input:

s = "abcdefghi", k = 3, fill = "x"

Output:

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

Explanation: The first 3 characters “abc” form the first group. The next 3 characters “def” form the second group. The last 3 characters “ghi” form the third group. Since all groups can be completely filled by characters from the string, we do not need to use fill. Thus, the groups formed are “abc”, “def”, and “ghi”.

Example 2

Input:

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

Output:

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

Explanation: Similar to the previous example, we are forming the first three groups “abc”, “def”, and “ghi”. For the last group, we can only use the character ‘j’ from the string. To complete this group, we add ‘x’ twice. Thus, the 4 groups formed are “abc”, “def”, “ghi”, and “jxx”.

Constraints

1 <= s.length <= 100
s consists of lowercase English letters.
1 <= k <= 100
fill is a lowercase English letter.

Iterative Simulation

Intuition We can iterate through the string with a step size of k. At each step, we extract a substring of length k. If the substring is shorter than k (which only happens at the very end), we manually append the fill character until it reaches the required length.

Steps

• Initialize an empty list to store the resulting groups.
• Iterate through the string s using a loop variable i starting from 0, incrementing by k in each step.
• Extract the substring from i to i + k.
• While the length of this substring is less than k, append the fill character to it.
• Add the processed substring to the result list.
• Return the result list.

class Solution:
    def divideString(self, s: str, k: int, fill: str) -> List[str]:
        res = []
        n = len(s)
        for i in range(0, n, k):
            group = s[i : i + k]
            while len(group) < k:
                group += fill
            res.append(group)
        return res

Complexity

• Time: O(n) where n is the length of the string. We visit each character once.
• Space: O(n) to store the result list.
• Notes: This is the most straightforward approach and works well for the given constraints.

Built-in Padding

Intuition Most modern programming languages provide built-in methods to pad strings to a specific length. We can leverage these functions to make the code cleaner and potentially more efficient by avoiding manual loops for the padding operation.

Steps

• Initialize an empty list for the result.
• Iterate through the string with a step of k.
• Extract the chunk of characters.
• Use the language’s built-in padding function (e.g., ljust, padEnd, or string repetition) to extend the chunk to length k using the fill character.
• Add the chunk to the result list and return it.

class Solution:
    def divideString(self, s: str, k: int, fill: str) -> List[str]:
        res = []
        n = len(s)
        for i in range(0, n, k):
            group = s[i : i + k]
            # Python specific: ljust pads the string on the right
            res.append(group.ljust(k, fill))
        return res

Complexity

• Time: O(n) where n is the length of the string.
• Space: O(n) to store the result.
• Notes: This approach is often preferred in production code for readability, utilizing standard library optimizations.