Problem

Given a text message and max number of characters, implement how the phone company can represent a given message.

OR

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.

Examples

Example 1:

1
2
3
4
5

Input: message = "hi k5kc, your uber is arriving now!", limit = 20
Output: [
	"hi k5kc, your u<1/3>",
	"ber is arriving<2/3>",
	" now!<3/3>"]

Example 2:

1
2
3
4
5
6
7

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.

Similar problem

Solution

Method 1 - Brute force

The brute-force solution is appropriate for this problem because it systematically checks for the minimum number of parts needed to split the message within the provided constraints. Unlike binary search, which relies on properties like monotonicity to reduce the search space efficiently, brute-force directly simulates and checks each possible number of parts sequentially.

Example Demonstration: Why Binary Search Fails

Example taken from Przemyslaw. Consider the message "abbababbbaaa aabaa a" with a character limit of 8. Using brute force, the process is as follows:

  1. Attempt with 1 Part:
    • Including the suffix "<1/1>" in the message, which is impossible because the suffix alone exceeds the character limit of 8.
  2. Attempt with 2 to 6 Parts:
    • Similar reasoning: each attempt adds a suffix "<a/b>", and these add up to exceed the limit or leave insufficient space in each part for the segments of the message.
  3. Attempt with 7 Parts:
    • The added suffix "<a/7>" becomes progressively feasible as parts increase, but binary search might miss this oddity.
    • Parts created: "abb<1/7>", "aba<2/7>", "bbb<3/7>", "aaa<4/7>", " a<5/7>", "ab<6/7>", "aa a<7/7>".
  4. Why Binary Search Fails:
    • Considering binary search property fails because parts succession isn’t strictly decreasing or increasing according to message length.
    • For example, 10 parts fail the size check after further iteration and incorrectly suggest previous lower blocks, skipping valid configurations intermediates, inadvertently pushing towards other invalid parts.

Brute force approach

The brute-force method systematically verifies each number of parts, ensuring accuracy and reliability given the problem constraints.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    public List<String> splitMessage(String message, int limit) {
        int msgLen = message.length();
        
        int parts = 1, totalLenIndex = 1; 
        
        while (parts * (digits(parts) + 3) + totalLenIndex + msgLen > parts * limit) {
            if (3 + digits(parts) * 2 >= limit) {
                return new ArrayList<>(); 
            }
            parts++;
            totalLenIndex += digits(parts);
        }
        
        List<String> ans = new ArrayList<>();
        int index = 0;
        for (int i = 1; i <= parts; i++) {
            int suffixLen = (digits(parts) + digits(i) + 3);
            int charsForPart = limit - suffixLen;
            if (index + charsForPart > msgLen) {
                charsForPart = msgLen - index;
            }
            String part = message.substring(index, index + charsForPart);
            ans.add(part + "<" + i + "/" + parts + ">");
            index += charsForPart;
        }
        
        return ans;
    }
    
    private int digits(int n) {
        return String.valueOf(n).length();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution:
    def split_message(self, msg: str, lim: int) -> List[str]:
        
        def size(n: int) -> int:                  
            return len(str(n))
        
        parts = total_len_index = 1
        msg_len = len(msg)
        
        while parts * (size(parts) + 3) + total_len_index + msg_len > parts * lim:
            if 3 + size(parts) * 2 >= lim:
                return []
            parts += 1
            total_len_index += size(parts)
        
        ans = []
        index = 0
        for i in range(1, parts + 1):
            suffix_len = size(parts) + size(i) + 3
            chars_for_part = lim - suffix_len
            if index + chars_for_part > msg_len:
                chars_for_part = msg_len - index
            part = msg[:chars_for_part]
            msg = msg[chars_for_part:]
            ans.append(f"{part}<{i}/{parts}>")
            index += chars_for_part
        
        return ans

Complexity

  • ⏰ Time complexity: O(n),  where n is the length of the message.
  • 🧺 Space complexity: O(n) for storing the resulting parts.