1156. Swap For Longest Repeated Character Substring

Problem

You are given a string text. You can swap two of the characters in the text.

Return the length of the longest substring with repeated characters.

  Example 1:

Input: text = "ababa"
Output: 3
Explanation: We can swap the first 'b' with the last 'a', or the last 'b' with the first 'a'. Then, the longest repeated character substring is "aaa" with length 3.

Example 2:

Input: text = "aaabaaa"
Output: 6
Explanation: Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring "aaaaaa" with length 6.

Example 3:

Input: text = "aaaaa"
Output: 5
Explanation: No need to swap, longest repeated character substring is "aaaaa" with length is 5.

  Constraints:

• 1 <= text.length <= 2 * 10^4

• text consist of lowercase English characters only.

Solution (Java)

class Solution {
    private static class Pair {
        char character;
        int count;

        public Pair(char c, int count) {
            this.character = c;
            this.count = count;
        }
    }

    public int maxRepOpt1(String text) {
        List<Pair> pairs = new ArrayList<>();
        Map<Character, Integer> map = new HashMap<>();
        // collect counts for each char-block
        int i = 0;
        while (i < text.length()) {
            char c = text.charAt(i);
            int count = 0;
            while (i < text.length() && text.charAt(i) == c) {
                count++;
                i++;
            }
            pairs.add(new Pair(c, count));
            map.put(c, map.getOrDefault(c, 0) + count);
        }
        int max = 0;
        // case 1, swap 1 item to the boundary of a consecutive cha-block to achieve possible max
        // length
        // we need total count to make sure whether a swap is possible!
        for (Pair p : pairs) {
            int totalCount = map.get(p.character);
            if (totalCount > p.count) {
                max = Math.max(max, p.count + 1);
            } else {
                max = Math.max(max, p.count);
            }
        }
        // case 2, find xxxxYxxxxx pattern
        // we need total count to make sure whether a swap is possible!
        for (int j = 1; j < pairs.size() - 1; j++) {
            if (pairs.get(j - 1).character == pairs.get(j + 1).character
                    && pairs.get(j).count == 1) {
                int totalCount = map.get(pairs.get(j - 1).character);
                int groupSum = pairs.get(j - 1).count + pairs.get(j + 1).count;
                if (totalCount > groupSum) {
                    max = Math.max(max, groupSum + 1);
                } else {
                    max = Math.max(max, groupSum);
                }
            }
        }
        return max;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).