# Divide a String Into Groups of Size k
**Difficulty:** EASY
[External](https://leetcode.com/problems/divide-a-string-into-groups-of-size-k)
Canonical: https://scaleengineer.com/dsa/problems/divide-a-string-into-groups-of-size-k
**Data structures:** String
**Companies:** [Canonical](https://scaleengineer.com/companies/canonical)
---
## Problem
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
## Iteration with Substring
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.
**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.
**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.
### Explanation
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:**
```java
class Solution {
    public String[] divideString(String s, int k, char fill) {
        int n = s.length();
        int numGroups = (n + k - 1) / k;
        String[] result = new String[numGroups];
        int resultIndex = 0;

        for (int i = 0; i < n; i += k) {
            int end = Math.min(i + k, n);
            String group = s.substring(i, end);

            if (group.length() < k) {
                StringBuilder sb = new StringBuilder(group);
                int remaining = k - group.length();
                for (int j = 0; j < remaining; j++) {
                    sb.append(fill);
                }
                result[resultIndex++] = sb.toString();
            } else {
                result[resultIndex++] = group;
            }
        }
        return result;
    }
}
```
### 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.

## Single Pass with StringBuilder
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.
**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).
**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.
### Explanation
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:**
```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public String[] divideString(String s, int k, char fill) {
        List<String> resultList = new ArrayList<>();
        StringBuilder currentGroup = new StringBuilder();

        for (char c : s.toCharArray()) {
            currentGroup.append(c);
            if (currentGroup.length() == k) {
                resultList.add(currentGroup.toString());
                currentGroup.setLength(0); // More efficient than new StringBuilder()
            }
        }

        // Handle the last group if it's not full
        if (currentGroup.length() > 0) {
            while (currentGroup.length() < k) {
                currentGroup.append(fill);
            }
            resultList.add(currentGroup.toString());
        }

        return resultList.toArray(new String[0]);
    }
}
```
### 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.

# Solutions
### Java

```java
class Solution {
public
  String[] divideString(String s, int k, char fill) {
    int n = s.length();
    String[] ans = new String[(n + k - 1) / k];
    if (n % k != 0) {
      s += String.valueOf(fill).repeat(k - n % k);
    }
    for (int i = 0; i < ans.length; ++i) {
      ans[i] = s.substring(i * k, (i + 1) * k);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<string> divideString(string s, int k, char fill) {
    int n = s.size();
    if (n % k)
      for (int i = 0; i < k - n % k; ++i)
        s.push_back(fill);
    vector<string> ans;
    for (int i = 0; i < s.size() / k; ++i)
      ans.push_back(s.substr(i * k, k));
    return ans;
  }
};

```

### Python

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

```