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.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6

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.

Solution

Method 1 – Simulation and Padding

Intuition

The problem is about splitting the string into chunks of size k. If the last chunk is smaller than k, we pad it with the fill character. This ensures all groups are of equal size, and reconstructing the string (removing fills) gives the original.

Approach

  1. Initialize an empty list/array to store the groups.
  2. Iterate over the string in steps of k.
  3. For each step, extract a substring of length k.
  4. If the substring is shorter than k, pad it with the fill character until its length is k.
  5. Add each group to the result list.
  6. Return the list of groups.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

func divideString(s string, k int, fill byte) []string {
  var ans []string
  for i := 0; i < len(s); i += k {
    end := i + k
    group := ""
    if end <= len(s) {
      group = s[i:end]
    } else {
      group = s[i:]
      for len(group) < k {
        group += string(fill)
      }
    }
    ans = append(ans, group)
  }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
  public String[] divideString(String s, int k, char fill) {
    List<String> ans = new ArrayList<>();
    for (int i = 0; i < s.length(); i += k) {
      String group;
      if (i + k <= s.length()) {
        group = s.substring(i, i + k);
      } else {
        group = s.substring(i);
        while (group.length() < k) {
          group += fill;
        }
      }
      ans.add(group);
    }
    return ans.toArray(new String[0]);
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
  fun divideString(s: String, k: Int, fill: Char): List<String> {
    val ans = mutableListOf<String>()
    var i = 0
    while (i < s.length) {
      var group = if (i + k <= s.length) s.substring(i, i + k) else s.substring(i)
      if (group.length < k) group += fill.toString().repeat(k - group.length)
      ans.add(group)
      i += k
    }
    return ans
  }
}
1
2
3
4
5
6
7
8
9

class Solution:
  def divideString(self, s: str, k: int, fill: str) -> list[str]:
    ans: list[str] = []
    for i in range(0, len(s), k):
      group = s[i:i+k]
      if len(group) < k:
        group += fill * (k - len(group))
      ans.append(group)
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
  pub fn divide_string(s: String, k: i32, fill: char) -> Vec<String> {
    let mut ans = Vec::new();
    let k = k as usize;
    let chars: Vec<char> = s.chars().collect();
    let n = chars.len();
    let mut i = 0;
    while i < n {
      let mut group: String = chars[i..std::cmp::min(i + k, n)].iter().collect();
      if group.len() < k {
        group.extend(std::iter::repeat(fill).take(k - group.len()));
      }
      ans.push(group);
      i += k;
    }
    ans
  }
}

Complexity

  • ⏰ Time complexity: O(n) — Each character is processed once.
  • 🧺 Space complexity: O(n) — Output list stores all groups.