Leetcode 2138: Divide a String Into Groups of Size k

Input: The input consists of a string `s` of lowercase English letters, an integer `k` representing the group size, and a `fill` character to complete the last group if necessary.

Example: Input: s = "hello", k = 3, fill = "z"

Constraints:

• 1 <= s.length <= 100

• 1 <= k <= 100

• fill is a lowercase English letter.

Output: The output is an array of strings, each representing a group formed by partitioning the input string `s` into parts of size `k`, with the last group potentially filled using the `fill` character.

Example: Output: ["hel", "loz"]

Constraints:

• The returned array will have as many elements as necessary to divide the string into groups of size `k`.

Goal: Partition the string into groups and handle the last group by appending the `fill` character if necessary.

Steps:

• Initialize an empty list for the result.

• Iterate through the string and divide it into groups of size `k`.

• If the last group contains fewer than `k` characters, append `fill` characters to complete it.

Goal: The input constraints ensure that the string can be processed within the problem's limits.

Steps:

• The length of the string is at most 100.

• The group size `k` is between 1 and 100.

• The `fill` character is a lowercase English letter.

Assumptions:

• The string contains only lowercase English letters.

• The input values for `k` and `fill` are valid.

• Input: s = "hello", k = 3, fill = "z"

• Explanation: The string is divided into two groups. The first group is 'hel'. The second group is 'lo', but since the length is less than `k`, we append 'z' to make it 'loz'.

Approach: To solve the problem, iterate through the string in steps of size `k`, create the groups, and handle the last group by filling it if necessary.

Observations:

• We need to divide the string into smaller chunks of size `k`. The last chunk may need additional characters to complete.

• Using a simple loop with string slicing or manual indexing will help form the groups. Special attention is needed for the last group to ensure it is filled properly.

Steps:

• Start by iterating through the string in increments of `k`.

• For each iteration, take a slice of `k` characters.

• If the slice is less than `k` characters, append the `fill` character to complete it.

• Add the completed group to the result list.

Empty Inputs:

• An empty string should return an empty list of groups.

Large Inputs:

• Test cases with maximum string lengths should be handled efficiently.

Special Values:

• When `k` is 1, each group is just a single character of the string.

Constraints:

• Ensure that the number of groups and the size of the last group are computed correctly.

vector<string> divideString(string s, int k, char fill) {
    vector<string> res((s.size() + k - 1) / k, string(k, fill));
    for (int i = 0; i < s.size(); ++i)
        res[i / k][i % k] = s[i];
    return res;
}

1 : Function Definition

vector<string> divideString(string s, int k, char fill) {

This is the function definition for `divideString`. It takes three parameters: a string `s`, an integer `k` (the size of each chunk), and a character `fill` to pad the chunks if necessary.

2 : Initialization

    vector<string> res((s.size() + k - 1) / k, string(k, fill));

This line initializes a vector `res` with enough rows to store the divided strings. The size of each row is `k`, and it is filled with the `fill` character. The number of rows is calculated by dividing the size of the input string by `k` and rounding up.

3 : Iteration

    for (int i = 0; i < s.size(); ++i)

This loop iterates over each character in the input string `s`.

4 : Filling the Matrix

        res[i / k][i % k] = s[i];

This line places the character `s[i]` into the appropriate position in the 2D vector `res`. The row is determined by `i / k` and the column by `i % k`.

5 : Return

    return res;

Once all characters have been placed into the vector, the function returns the 2D vector `res`.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is linear in relation to the size of the string, as we process each character exactly once.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is also linear, as we store the result array, which has a size proportional to the input string.

Leetcode 2138: Divide a String Into Groups of Size k

Explore →