[Java] Binary Search for Message Partitioning. Beats 92.48% runtime and 96.08% memory
IntuitionYou can use binary search to determine the optimal number of parts, initially ranging from 1 to message.length(). Additionally, you can calculate the l
# Intuition
You can use binary search to determine the optimal number of parts, initially ranging from 1 to message.length(). Additionally, you can calculate the length of the first segment to extract, given that each part has a fixed length:
```
int x = limit - 4 - l;
```
Here, 4 accounts for the characters '<', '1', '/', and '>', which are always present in the first part. The variable l represents the length of the total number of parts in digits (e.g., if there are 367 parts, then l = 3).

# Approach
First, determine the number of parts using binary search, similar to Leetcode 1891: Cutting Ribbons. Note that if an m-part partition is not feasible, you won’t know which side contains the valid answer, so both halves must still be explored.

Once the number of parts is determined, split the message accordingly.

# Complexity
- Time complexity:
$$O(n)$$

- Space complexity:
$$O(n)$$

# Code
```java []
class Solution {
    private String message;
    private int limit;
    private int res = Integer.MAX_VALUE;
    public String[] splitMessage(String message, int limit) {
        if (limit <= 5) {
            return new String[0];
        }
        this.message = message;
        this.limit = limit;
        bs(1, message.length());
        return res != Integer.MAX_VALUE ? split(res) : new String[0];
    }
    private void bs(int l, int r) {
        if (l > r) {
            return;
        }
        int m = (l + r) / 2;
        if (possible(m)) {
            res = Math.min(res, m);
            bs(l, m - 1);
        } else {
            bs(l, m - 1);
            bs(m + 1, r);
        }
    }
    private boolean possible(int m) {
        int l = Integer.toString(m).length();
        int p = message.length();
        int x = limit - 4 - l;
        if (1 <= m && m <= 9) {
            p -= (m - 1) * x;
        } else if (10 <= m && m <= 99) {
            p -= (m - 1) * x - m + 10;
        } else if (100 <= m && m <= 999) {
            p -= (m - 1) * x - 2 * m + 110;
        } else if (1000 <= m && m <= 9999) {
            p -= (m - 1) * x - 3 * m + 1110;
        } else {
            p -= (m - 1) * x - 4 * m + 11110;
        }
        return p + 2 * l + 3 <= limit;
    }
    private String[] split(int m) {
        int l = Integer.toString(m).length();
        int x = limit - 4 - l;
        String[] res = new String[m];
        int i = 0;
        for (int k = 1; k < m; k++) {
            StringBuilder sb = new StringBuilder();
            int t = x;
            if (10 <= k && k <= 99) {
                t -= 1;
            } else if (100 <= k && k <= 999) {
                t -= 2;
            } else if (1000 <= k && k <= 9999) {
                t -= 3;
            }
            sb.append(message.substring(i, i + t));
            sb.append("<");
            sb.append(k);
            sb.append("/");
            sb.append(m);
            sb.append(">");
            res[k - 1] = sb.toString();
            i = i + t;
        }
        StringBuilder sb = new StringBuilder();
        sb.append(message.substring(i));
        sb.append("<");
        sb.append(m);
        sb.append("/");
        sb.append(m);
        sb.append(">");
        res[m - 1] = sb.toString();
        return res;
    }
}
```
['Java']