2138. Divide a String Into Groups of Size k

Difficulty: Easy

Topics: String, Simulation

Companies: Google, Amazon, Microsoft

Problem Statement

Given a string s, an integer k, and a character fill, partition the string into groups of size k as follows:

The first group consists of the first k characters
The second group consists of the next k characters
Continue this process until all characters are used
For the last group, if there aren't enough characters, complete it using the fill character

Return an array of strings representing all groups after partitioning.

Example 1

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

Example 2

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

Problem Link: View on LeetCode ↗

Approach 1: Substring with Padding (Brute Force)

This approach processes the string by taking substrings of length k and pads the last group if needed.

Algorithm Steps

Initialize an empty result list
Calculate the number of complete groups: n = s.length() / k
For each complete group, take a substring of length k and add to result
For the last group:
- Take the remaining substring
- Add fill characters until length equals k
- Add this group to result

Substring with Padding

class Solution {
public:
    vector<string> divideString(string s, int k, char fill) {
        vector<string> res;
        int n = s.length();
        int completeGroups = n / k;
        
        // Process complete groups
        for (int i = 0; i < completeGroups; i++) {
            res.push_back(s.substr(i * k, k));
        }
        
        // Handle last group
        if (n % k != 0) {
            string last = s.substr(completeGroups * k);
            while (last.length() < k) {
                last += fill;
            }
            res.push_back(last);
        }
        return res;
    }
};

class Solution {
    public String[] divideString(String s, int k, char fill) {
        int n = s.length();
        int groups = (n + k - 1) / k; // Ceiling division
        String[] res = new String[groups];
        
        // Process each group
        for (int i = 0; i < groups; i++) {
            int start = i * k;
            int end = Math.min(start + k, n);
            String group = s.substring(start, end);
            
            // Pad if necessary
            if (group.length() < k) {
                group += String.valueOf(fill).repeat(k - group.length());
            }
            res[i] = group;
        }
        return res;
    }
}

class Solution:
    def divideString(self, s: str, k: int, fill: str) -> List[str]:
        n = len(s)
        groups = (n + k - 1) // k  # Ceiling division
        res = []
        
        for i in range(groups):
            start = i * k
            end = min(start + k, n)
            group = s[start:end]
            
            # Pad if necessary
            if len(group) < k:
                group += fill * (k - len(group))
            res.append(group)
            
        return res

Complexity: O(n) time, O(n) space

Approach 2: Two-Pointer Technique

This approach uses two pointers to efficiently traverse the string and form groups.

Algorithm Steps

Initialize two pointers: start = 0 and end = k-1
While end is within the string length:
- Extract substring from start to end
- Add to result list
- Move pointers: start = end + 1, end += k
After loop, check if any characters remain:
- Take substring from start to end of string
- Pad with fill to make length k
- Add to result

Two-Pointer Technique

class Solution {
public:
    vector<string> divideString(string s, int k, char fill) {
        vector<string> res;
        int start = 0;
        int end = k - 1;
        int n = s.length();
        
        while (end < n) {
            res.push_back(s.substr(start, k));
            start = end + 1;
            end += k;
        }
        
        if (start < n) {
            string last = s.substr(start);
            while (last.length() < k) {
                last += fill;
            }
            res.push_back(last);
        }
        
        return res;
    }
};

class Solution {
    public String[] divideString(String s, int k, char fill) {
        List<String> res = new ArrayList<>();
        int start = 0;
        int end = k - 1;
        int n = s.length();
        
        while (end < n) {
            res.add(s.substring(start, end + 1));
            start = end + 1;
            end += k;
        }
        
        if (start < n) {
            String last = s.substring(start);
            while (last.length() < k) {
                last += fill;
            }
            res.add(last);
        }
        
        return res.toArray(new String[0]);
    }
}

class Solution:
    def divideString(self, s: str, k: int, fill: str) -> List[str]:
        res = []
        start = 0
        n = len(s)
        
        while start < n:
            end = start + k
            if end <= n:
                res.append(s[start:end])
            else:
                group = s[start:]
                group += fill * (k - len(group))
                res.append(group)
            start = end
            
        return res

Complexity: O(n) time, O(n) space

Approach 3: Iterative Character Collection

This approach builds each group character by character, which is efficient and easy to understand.

Algorithm Steps

Initialize an empty result list and a temporary string for current group
Iterate through each character in the string:
- Add character to current group
- When group reaches size k, add to result and reset group
After iteration, if there's an incomplete group:
- Pad with fill until length is k
- Add to result

Iterative Character Collection

class Solution {
public:
    vector<string> divideString(string s, int k, char fill) {
        vector<string> res;
        string current;
        
        for (char c : s) {
            current += c;
            if (current.size() == k) {
                res.push_back(current);
                current = "";
            }
        }
        
        if (!current.empty()) {
            while (current.size() < k) {
                current += fill;
            }
            res.push_back(current);
        }
        
        return res;
    }
};

class Solution {
    public String[] divideString(String s, int k, char fill) {
        List<String> res = new ArrayList<>();
        StringBuilder current = new StringBuilder();
        
        for (char c : s.toCharArray()) {
            current.append(c);
            if (current.length() == k) {
                res.add(current.toString());
                current = new StringBuilder();
            }
        }
        
        if (current.length() > 0) {
            while (current.length() < k) {
                current.append(fill);
            }
            res.add(current.toString());
        }
        
        return res.toArray(new String[0]);
    }
}

class Solution:
    def divideString(self, s: str, k: int, fill: str) -> List[str]:
        res = []
        current = []
        
        for c in s:
            current.append(c)
            if len(current) == k:
                res.append(''.join(current))
                current = []
                
        if current:
            res.append(''.join(current) + fill * (k - len(current)))
            
        return res

Optimized: Efficient for memory with O(k) space for current group

Approach 4: Mathematical Grouping

This approach calculates the exact number of groups needed and processes them mathematically.

Algorithm Steps

Calculate total groups: groups = ceil(s.length / k)
Initialize result array with empty strings
For each group index i:
- Calculate start index: i * k
- Calculate end index: min((i+1)*k, n)
- Extract substring from start to end
- Pad to length k if needed

Mathematical Grouping

class Solution {
public:
    vector<string> divideString(string s, int k, char fill) {
        int n = s.size();
        int groups = (n + k - 1) / k; // Ceiling division
        vector<string> res(groups);
        
        for (int i = 0; i < groups; i++) {
            int start = i * k;
            int end = min(start + k, n);
            res[i] = s.substr(start, end - start);
            
            if (res[i].size() < k) {
                res[i] += string(k - res[i].size(), fill);
            }
        }
        return res;
    }
};

class Solution {
    public String[] divideString(String s, int k, char fill) {
        int n = s.length();
        int groups = (n + k - 1) / k; // Ceiling division
        String[] res = new String[groups];
        
        for (int i = 0; i < groups; i++) {
            int start = i * k;
            int end = Math.min(start + k, n);
            res[i] = s.substring(start, end);
            
            if (res[i].length() < k) {
                res[i] += String.valueOf(fill).repeat(k - res[i].length());
            }
        }
        return res;
    }
}

class Solution:
    def divideString(self, s: str, k: int, fill: str) -> List[str]:
        n = len(s)
        groups = (n + k - 1) // k  # Ceiling division
        res = [''] * groups
        
        for i in range(groups):
            start = i * k
            end = min(start + k, n)
            res[i] = s[start:end]
            if len(res[i]) < k:
                res[i] += fill * (k - len(res[i]))
                
        return res

Efficiency: O(n) time, O(n) space with minimal overhead

Approach Comparison

Approach	Time	Space	Best For
Substring with Padding	O(n)	O(n)	Readability
Two-Pointer	O(n)	O(n)	Learning purposes
Iterative Collection	O(n)	O(k)	Memory efficiency
Mathematical	O(n)	O(n)	Performance

Recommendation: Mathematical approach is most efficient for large inputs

Edge Cases

1. String length exactly divisible by k

Input: s = "abcd", k = 2, fill = 'x'
Output: ["ab","cd"]

2. String shorter than k

Input: s = "a", k = 4, fill = 'x'
Output: ["axxx"]

3. Empty string

Input: s = "", k = 3, fill = 'x' → Output: ["xxx"] (but constraints prevent this)

4. k = 1

Input: s = "abc", k = 1, fill = 'x'
Output: ["a","b","c"]

Important: Always handle the last group padding correctly

Frequently Asked Questions

What if k is larger than the string length?

The entire string becomes the first group, padded with fill characters to reach length k.

How do we calculate the number of groups?

Use ceiling division: groups = (n + k - 1) / k, which ensures we account for partial groups.

Can we solve this with constant space?

No, since we need to store all groups, which requires O(n) space.

Which approach is most efficient?

All approaches are O(n) time, but the mathematical approach has minimal overhead.

How does padding work with multi-character fill?

The problem specifies fill is a single character, so we repeat that character.

What if fill character is part of the string?

It doesn't matter - we only add fill characters to incomplete groups at the end.

Can we modify the string in-place?

No, since strings are immutable in many languages. We need to create new strings/groups.

How to handle k = 0?

Constraints ensure k ≥ 1, so no need to handle k = 0.

What's the best approach for very large strings?

The mathematical approach is most efficient as it minimizes operations.

Can we use recursion?

Yes, but iterative approaches are more efficient and avoid stack overflow.

How does the solution handle Unicode characters?

The problem specifies lowercase English letters, but solutions work with any characters.

Is there a one-line solution?

In Python: [s[i*k:(i+1)*k].ljust(k, fill) for i in range((len(s)+k-1)//k)]

Final Recommendation: The mathematical approach provides the best combination of efficiency and readability.