Divide a String Into Groups of Size k

Problem Statement

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 groups has been divided into, using the above procedure.

Examples

Example 1:

Input: s = "abcdefghi", k = 3, fill = "x"
Output: ["abc", "def", "ghi"]

Expalantion:
The The first 3 characters "abc" form the first group.
The next 3 characters "def" form the second group.
Since all groups can be completely filled by characters from the string, we do not need to use fill.
Thus, the group 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.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

We want to cut the string into equal parts of size k.

• Every full k characters becomes one group.
• If the last part has fewer than k characters, we pad it with fill until its length becomes k.

This ensures that:

• Every group has exactly k characters.
• The original string is recoverable by joining the groups and removing the trailing fill characters if needed.

Approach:

1. Loop over the string in steps of size k.
2. For each step:
   1. Create a substring of the next k characters.
   2. If fewer than k characters are left, pad with fill characters.
3. Add each group to a result vector.
4. Return the vector.

Code:

class Solution {
public:
    vector<string> divideString(string s, int k, char fill) {
        vector<string> result;
        int n = s.length();

        for (int i = 0; i < n; i += k) {
            string group;

            // Collect next k characters or fill if beyond length
            for (int j = i; j < i + k; ++j) {
                if (j < n)
                    group += s[j];
                else
                    group += fill;
            }

            result.push_back(group);
        }

        return result;
    }
};

Complexity Analysis:

• Time Complexity:O(n)
  • Each character is processed exactly once.
• Space Complexity:O(n/k) + O(n)
  • Result stores n/k string of length k, plus temp string in memory.