2468. Split Message Based on Limit

  • Hardness: \(\color{red}\textsf{Hard}\)
  • Ralated Topics: String、Binary Search
  • \(\color{blue}\textsf{Biweekly Contest 91}\)

一、題目

You are given a string, message, and a positive integer, limit.

You must split message into one or more parts based on limit. Each resulting part should have the suffix "<a/b>", where "b" is to be replaced with the total number of parts and "a" is to be replaced with the index of the part, starting from 1 and going up to b. Additionally, the length of each resulting part (including its suffix) should be equal to limit, except for the last part whose length can be at most limit.

The resulting parts should be formed such that when their suffixes are removed and they are all concatenated in order, they should be equal to message. Also, the result should contain as few parts as possible.

Return the parts message would be split into as an array of strings. If it is impossible to split message as required, return an empty array.

Example 1:

  • input: message = “this is really a very awesome message”, limit = 9
  • Output: [“thi<1/14>”,“s i<2/14>”,“s r<3/14>”,“eal<4/14>”,“ly <5/14>”,“a v<6/14>”,“ery<7/14>”," aw<8/14>",“eso<9/14>”,“me<10/14>”," m<11/14>",“es<12/14>”,“sa<13/14>”,“ge<14/14>”]
  • Explanation:
    The first 9 parts take 3 characters each from the beginning of message.
    The next 5 parts take 2 characters each to finish splitting message.
    In this example, each part, including the last, has length 9.
    It can be shown it is not possible to split message into less than 14 parts.

Example 2:

  • Input: message = “short message”, limit = 15
  • Output: [“short mess<1/2>”,“age<2/2>”]
  • Explanation:
    Under the given constraints, the string can be split into two parts:
  • The first part comprises of the first 10 characters, and has a length 15.
  • The next part comprises of the last 3 characters, and has a length 8.

Constraints:

  • 1 <= message.length <= 10^4
  • message consists only of lowercase English letters and ' '.
  • 1 <= limit <= 10^4

二、分析

  • 令 n 為最後答案 vector 的總數，注意並非 n 愈大，能裝載的 string 就愈多。
  • limit * n >= f(n) + len 時，message 可以被裝載，其中 len 為其長度，f(n)為 n 時所需額外的字元長度。
  • 觀察可得 f(n) 為：
    • n < 10 時，5*n。
    • n < 100 時，7*n - 9。
    • n < 1000 時，9*n - 9 - 99。
    • n < 10000 時，11*n - 9 - 99 - 999。
    • …

三、解題

1. Math

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(n)\)
    vector<string> splitMessage(string message, int limit) {
    if (limit <= 5) return {};
    int len = message.length();
    int left = 1;
    for ( ;left < len; left++) {
        if (limit * left >= f(left) + len) break;
    }
    if (limit * left < f(left) + len) return {};
    vector<string> res(left);
    int strlen = to_string(left).length() + 3;
    int acc = 0;
    for (int i = 1; i <= left; i++) {
        len = strlen + to_string(i).length();
        res[i-1] = message.substr(acc, limit-len) + "<" + to_string(i) + "/" + to_string(left) + ">";
        acc += limit-len;
    }
    return res;
}
int f(int n) {
    if (n < 10) {
        return n*5;
    } else if (n < 100) {
        return n*7-9;
    } else if (n < 1000) {
        return n*9-108;
    } else if (n < 10000) {
        return n*11-1107;
    }
    return n*13-11106;
}
  • Time complexity: \(O(\log n)\)
  • Space complexity: \(O(n)\)
vector<string> splitMessage(string message, int limit) {
    int b = 0 , cnt = 0 , sm = 0;
    vector<string> ans;
    for(int i=1; i<=10000; i++) {
        sm+=Size(i);  // sum of length of ('1') + ('2')... ('i')  , we are calculating sum of length of all a's.
        int cnt = ((3 + Size(i)) * i) + message.size() + sm;   // sum of (3 is "</>"  + i's size ) * i times , message , sm 
        int len = (i-1) * limit; // till second last
        if(cnt - len <= limit) {  // if last is bigger than limit , its invalid!
            b = i;
            break;
        }
    }
    string s = "";
    cnt = 1;
    for(int i=0; i<message.size(); i++) {
            if(limit - (3 + Size(cnt) + Size(b) + (int)s.size())>0) {
                s+=message[i];
            }else {
                string word = s + "<" + to_string(cnt) + "/" + to_string(b) + ">";
                ans.push_back(word);
                s = message[i];
                cnt++;
            }
    }
        string word = s + "<" + to_string(cnt) + "/" + to_string(b) + ">";
        ans.push_back(word);
        if(cnt>b || word.size()>limit) return {};   // cnt is last value of a which should never be > than b , also last word size should be <= limit!
    return ans;
}
int Size(int n) {
    return to_string(n).size();
}

回目錄 Catalog