We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Split Message Based on Limit

Number: 2563

Difficulty: Hard

Paid? No

Companies: Uber, Databricks, Capital One, Roblox, Meta, TikTok

Problem Description

Given a string message and an integer limit, the goal is to split message into one or more parts such that: • Each part contains a suffix of the form "<a/b>" where "b" is the total number of parts and "a" is the 1-indexed part number. • Every part (except possibly the last) must have exactly length equal to limit (including the suffix), whereas the last part’s length can be at most limit. • When the suffixes are removed and the parts are concatenated in order, they should equal the original message. • The number of parts must be minimized. Return an empty array if it is impossible to split under these constraints.

Key Insights

  • The suffix for each part is dynamic: its length is 3 + (number of digits in a) + (number of digits in b). Notice that, while b is fixed for a candidate split, a varies from 1 to b.
  • All parts (except the last) must fill the "limit" exactly. Thus, for each part i (i < b), the number of message characters available is (limit - (3 + digitCount(i) + digitCount(b))).
  • The last part has a flexible length – its message content length must be ≤ (limit - (3 + digitCount(b) + digitCount(b))).
  • To determine the minimum number of parts b, we need to try candidate values and check if the sum of fixed capacities of parts 1..(b-1) and the capacity of the last part can exactly cover the message length.
  • A brute‐force iteration over b (up to message.length) is acceptable given the problem constraints.

Space and Time Complexity

Time Complexity: O(b) per candidate where b can be up to O(L) in the worst-case; overall O(L^2) in the worst scenario. However, typically b is much smaller.
Space Complexity: O(L) for storing the resulting parts.

Solution

We first iterate over possible numbers of parts (from 1 upwards) and, for each candidate b, compute:

  1. For parts 1 to b–1, the fixed available capacity = limit – (3 + digitCount(i) + digitCount(b)). If any capacity is negative, that candidate fails.
  2. Sum these capacities (sumFixed) and compute the maximum capacity available in the last part = limit – (3 + digitCount(b) + digitCount(b)).
  3. Check if the message length L satisfies: sumFixed ≤ L ≤ sumFixed + capacity_last.
    Once we find the minimal b satisfying this, we reconstruct every part by: • For each part i (1 <= i < b), taking exactly (limit – (3 + digitCount(i) + digitCount(b))) characters from message and appending the suffix "<i/b>". • For the last part, taking the remaining characters ensuring the final length (content + suffix) is ≤ limit. Key data structures used include simple counters and string slicing, and the approach is an enumeration over possible parts combined with simulation to rebuild the answer.

Code Solutions

# Python solution for splitting the message based on limit.
def splitMessage(message, limit):
    message_length = len(message)
    
    # Helper function to count digits
    def digit_count(num):
        return len(str(num))
    
    # Try possible number of parts (b) from 1 to message_length (upper bound)
    for total_parts in range(1, message_length + 1):
        digits_total = digit_count(total_parts)
        fixed_capacity = 0
        valid = True
        # Calculate capacity for parts 1 to total_parts - 1
        for part in range(1, total_parts):
            capacity = limit - (3 + digit_count(part) + digits_total)
            if capacity < 0:
                valid = False
                break
            fixed_capacity += capacity
        
        # Compute capacity of the last part (part number = total_parts)
        last_capacity = limit - (3 + digits_total + digits_total)
        if last_capacity < 0:
            valid = False
        
        # Check if the current candidate total_parts can cover the message length.
        if valid and fixed_capacity <= message_length <= fixed_capacity + last_capacity:
            # We have a valid split. Now, construct the answer.
            parts = []
            current_index = 0
            # Process parts 1 to total_parts - 1
            for part in range(1, total_parts):
                capacity = limit - (3 + digit_count(part) + digits_total)
                # Take exactly 'capacity' characters for non-last parts.
                part_message = message[current_index: current_index + capacity]
                current_index += capacity
                suffix = "<" + str(part) + "/" + str(total_parts) + ">"
                parts.append(part_message + suffix)
            # Last part takes the remaining characters.
            remaining_message = message[current_index:]
            suffix = "<" + str(total_parts) + "/" + str(total_parts) + ">"
            parts.append(remaining_message + suffix)
            return parts
    return []  # return empty if no valid split is found

# Example usage:
#print(splitMessage("this is really a very awesome message", 9))
#print(splitMessage("short message", 15))
← Back to All Questions