algoadvance

Leetcode 2138. Divide a String Into Groups of Size k

Problem Statement

You are given a string s and an integer k. You need to divide the string into groups of size k. If the string is not of size multiple of k, the final group will have fewer characters. However, for this problem, you should fill the remaining characters of the last group with the fill character to make its length equal to k.

You need to return a list of strings, each of the length k, except perhaps for the last group which may be padded if needed.

Example:

Clarifying Questions

  1. What is the range of values for s and k?
    • s is any string (a sequence of alphanumeric characters).
    • k is an integer such that 1 <= k <= len(s).
  2. What should be done if s is already a multiple of k?
    • Simply split s into groups of k.
  3. Is it guaranteed that s and fill will contain only ASCII characters?
    • Yes.
  4. Can fill character be the same as characters already present in the string?
    • Yes, fill can be any character, including ones that are present in s.

Strategy

  1. Initialize an empty vector of strings to store the result.
  2. Iterate over the input string s in steps of k.
  3. For each step, extract a substring of length k and add it to the result.
  4. After the loop, check if the last substring added has length less than k. If so, pad it with the fill character until it reaches length k.
  5. Return the result vector of strings.

Code

Here is the C++ implementation for the described strategy:

#include <iostream>
#include <vector>
#include <string>

std::vector<std::string> divideString(std::string s, int k, char fill) {
    std::vector<std::string> result;
    int n = s.length();
    
    for (int i = 0; i < n; i += k) {
        std::string part = s.substr(i, k);
        if (part.length() < k) {
            part.append(k - part.length(), fill);
        }
        result.push_back(part);
    }
    
    return result;
}

int main() {
    std::string s = "abcdefgh";
    int k = 3;
    char fill = 'x';
    std::vector<std::string> result = divideString(s, k, fill);
    
    for (const std::string& str : result) {
        std::cout << "\"" << str << "\" ";
    }
    
    return 0;
}

Time Complexity

The time complexity for this solution is O(n), where n is the length of the input string s. This is because we iterate over each character in the input string exactly once. Substring operations and padding require a split and append which also run in linear time relative to the size of the substring being processed, thus keeping the overall complexity linear.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI