Divide a String Into Groups of Size k

Easy

#1948Time: O(N), where N is the length of the string `s`. The main loop runs `N/k` times. Inside the loop, `s.substring()` takes O(k) time to copy characters, and padding also takes at most O(k) time. The total time complexity is `(N/k) * O(k) = O(N)`.Space: O(N), where N is the length of the string `s`. This space is primarily for the output array, which stores strings whose total length is at least N.1 company

Data structures

String

Companies

Canonical

Prompt

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 the string, the second group consists of the next k characters of the string, and so on. Each element can be a part of exactly one group.
For the last group, if the string does not have k characters remaining, a character fill is used to complete the group.

Note that the partition is done so that after removing the fill character from the last group (if it exists) and concatenating all the groups in order, the resultant string should be s.

Given the string s, the size of each group k and the character fill, return a string array denoting the composition of every group s has been divided into, using the above procedure.

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 only.
1 <= k <= 100
fill is a lowercase English letter.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through the string s with a step size of k. In each step, it extracts a substring of length k. If the last substring is shorter than k, it's padded with the fill character.

Algorithm

Calculate the total number of groups required: (s.length() + k - 1) / k.
Create a string array result of this size.
Loop through the string s with an index i starting at 0 and incrementing by k.
In each iteration, get the substring from i to min(i + k, s.length()).
If the substring length is less than k, pad it with the fill character using a StringBuilder.
Add the (potentially padded) group to the result array.
Return the result array.

Walkthrough

This method directly implements the grouping logic by stepping through the string in chunks of size k.

Algorithm:
1. First, determine the number of groups that will be created. This is the length of the string s divided by k, rounded up. In integer arithmetic, this can be calculated as (s.length() + k - 1) / k.
2. Create a string array result of this calculated size to store the groups.
3. Iterate through the string s using an index i that starts at 0 and increments by k in each step (i += k).
4. In each iteration, extract the substring for the current group. The substring starts at index i and ends at min(i + k, s.length()). This handles the case where the last group might be smaller than k.
5. If the extracted substring's length is less than k, it means we are at the last group and it needs padding. A StringBuilder is used to append the fill character the required number of times.
6. If the substring's length is exactly k, it can be used as is.
7. Store the resulting group string (padded or not) in the result array.
8. After the loop completes, return the result array.
Code Snippet:

1class Solution {2    public String[] divideString(String s, int k, char fill) {3        int n = s.length();4        int numGroups = (n + k - 1) / k;5        String[] result = new String[numGroups];6        int resultIndex = 0;7 8        for (int i = 0; i < n; i += k) {9            int end = Math.min(i + k, n);10            String group = s.substring(i, end);11 12            if (group.length() < k) {13                StringBuilder sb = new StringBuilder(group);14                int remaining = k - group.length();15                for (int j = 0; j < remaining; j++) {16                    sb.append(fill);17                }18                result[resultIndex++] = sb.toString();19            } else {20                result[resultIndex++] = group;21            }22        }23        return result;24    }25}

Complexity

Time

O(N), where N is the length of the string `s`. The main loop runs `N/k` times. Inside the loop, `s.substring()` takes O(k) time to copy characters, and padding also takes at most O(k) time. The total time complexity is `(N/k) * O(k) = O(N)`.

Space

O(N), where N is the length of the string `s`. This space is primarily for the output array, which stores strings whose total length is at least N.

Trade-offs

Pros

The code is highly readable and directly translates the problem statement into logic.
It's a very straightforward and easy-to-understand implementation.

Cons

Creating a new substring object in each iteration can introduce a slight performance overhead due to object creation and memory copying, especially compared to a single-pass approach.

This approach iterates through the input string character by character only once, building each group in a StringBuilder. When a group is complete, it's added to the result list, and the StringBuilder is reset for the next group. This is generally more efficient as it avoids creating multiple intermediate substring objects.

Algorithm

Initialize an ArrayList<String> and an empty StringBuilder currentGroup.
Iterate through each character of the input string s.
Append the character to currentGroup.
If currentGroup.length() equals k, add its string representation to the list and reset currentGroup.
After the loop, if currentGroup is not empty, pad it with the fill character until its length is k.
Add the final group to the list.
Convert the list to a string array and return it.

Walkthrough

This optimized approach avoids repeated substring creation by building the groups directly while iterating through the input string once.

Algorithm:
1. Initialize an ArrayList<String> to dynamically store the resulting groups.
2. Initialize an empty StringBuilder named currentGroup.
3. Iterate through the input string s from the first character to the last.
4. For each character, append it to the currentGroup.
5. After appending, check if the length of currentGroup has reached k.
6. If it has, a complete group has been formed. Convert currentGroup to a string, add it to the result list, and reset currentGroup (e.g., by calling setLength(0)).
7. After the loop finishes, check if currentGroup contains any characters. This happens if the total length of s is not a multiple of k.
8. If currentGroup is not empty, it represents the last, incomplete group. Pad it by appending the fill character until its length becomes k.
9. Add this final, padded group to the result list.
10. Finally, convert the list of strings into a string array and return it.
Code Snippet:

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public String[] divideString(String s, int k, char fill) {6        List<String> resultList = new ArrayList<>();7        StringBuilder currentGroup = new StringBuilder();8 9        for (char c : s.toCharArray()) {10            currentGroup.append(c);11            if (currentGroup.length() == k) {12                resultList.add(currentGroup.toString());13                currentGroup.setLength(0); // More efficient than new StringBuilder()14            }15        }16 17        // Handle the last group if it's not full18        if (currentGroup.length() > 0) {19            while (currentGroup.length() < k) {20                currentGroup.append(fill);21            }22            resultList.add(currentGroup.toString());23        }24 25        return resultList.toArray(new String[0]);26    }27}

Complexity

Time

O(N), where N is the length of the string `s`. The string is traversed only once. Appending to a `StringBuilder` is an amortized O(1) operation. The total time is dominated by the single pass through the string.

Space

O(N), where N is the length of the string `s`. O(N) space is required for the output list/array. The auxiliary space used by the `StringBuilder` is O(k).

Trade-offs

Pros

More memory and time-efficient as it avoids creating new substring objects for each group.
Processes the string in a single, continuous pass.

Cons

The logic can be slightly more complex to follow than the direct substring approach, as it involves managing the state of the StringBuilder and handling the final partial group as a separate case after the loop.

Solutions

Solution

1class Solution {2public3  String[] divideString(String s, int k, char fill) {4    int n = s.length();5    String[] ans = new String[(n + k - 1) / k];6    if (n % k != 0) {7      s += String.valueOf(fill).repeat(k - n % k);8    }9    for (int i = 0; i < ans.length; ++i) {10      ans[i] = s.substring(i * k, (i + 1) * k);11    }12    return ans;13  }14}

1class Solution {2public:3  vector<string> divideString(string s, int k, char fill) {4    int n = s.size();5    if (n % k)6      for (int i = 0; i < k - n % k; ++i)7        s.push_back(fill);8    vector<string> ans;9    for (int i = 0; i < s.size() / k; ++i)10      ans.push_back(s.substr(i * k, k));11    return ans;12  }13};

1class Solution:2    def divideString(self, s: str, k: int, fill: str) -> List[str]: return [3        s[i: i + k]. ljust(k, fill) for i in range(0, len(s), k)]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem