Skip to content

3714. Longest Balanced Substring II

Description

You are given a string s consisting only of the characters 'a', 'b', and 'c'.

A substring of s is called balanced if all distinct characters in the substring appear the same number of times.

Return the length of the longest balanced substring of s.

Β 

Example 1:

Input: s = "abbac"

Output: 4

Explanation:

The longest balanced substring is "abba" because both distinct characters 'a' and 'b' each appear exactly 2 times.

Example 2:

Input: s = "aabcc"

Output: 3

Explanation:

The longest balanced substring is "abc" because all distinct characters 'a', 'b' and 'c' each appear exactly 1 time.

Example 3:

Input: s = "aba"

Output: 2

Explanation:

One of the longest balanced substrings is "ab" because both distinct characters 'a' and 'b' each appear exactly 1 time. Another longest balanced substring is "ba".

Β 

Constraints:

  • 1 <= s.length <= 105
  • s contains only the characters 'a', 'b', and 'c'.

Solutions

Solution 1: Enumeration + Prefix Sum + Hash Table

The answer is divided into the following three cases:

  1. Balanced substring with only one character, such as "aaa".
  2. Balanced substring with two characters, such as "aabb".
  3. Balanced substring with three characters, such as "abc".

We define three functions \(\text{calc1}(s)\), \(\text{calc2}(s, a, b)\), and \(\text{calc3}(s)\) to calculate the longest balanced substring length for the above three cases respectively, and finally return the maximum of the three.

For \(\text{calc1}(s)\), we only need to traverse the string \(s\), count the length of each consecutive character, and take the maximum value.

For \(\text{calc2}(s, a, b)\), we can use prefix sum and hash table to calculate the longest balanced substring length. Specifically, we maintain a variable \(d\) to represent the number of character \(a\) minus the number of character \(b\) in the current substring, and use a hash table to record the first occurrence position of each \(d\) value. When we encounter the same \(d\) value again, it means that the number of character \(a\) and character \(b\) in the substring from the last occurrence position to the current position are equal, i.e., the substring is balanced, and we update the answer.

For \(\text{calc3}(s)\), we also use prefix sum and hash table to calculate the longest balanced substring length. We define an array \(\textit{cnt}\) to record the counts of characters \(a\), \(b\), and \(c\), and use a hash table to record the first occurrence position of each \((\textit{cnt}[a] - \textit{cnt}[b], \textit{cnt}[b] - \textit{cnt}[c])\) value. When we encounter the same value again, it means that the counts of characters \(a\), \(b\), and \(c\) in the substring from the last occurrence position to the current position are equal, i.e., the substring is balanced, and we update the answer.

Finally, we calculate the values of \(\text{calc1}(s)\), \(\text{calc2}(s, 'a', 'b')\), \(\text{calc2}(s, 'b', 'c')\), \(\text{calc2}(s, 'a', 'c')\), and \(\text{calc3}(s)\) respectively, and return their maximum value.

The time complexity is \(O(n)\) and the space complexity is \(O(n)\), where \(n\) is the length of the string \(s\).

 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
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution:
    def longestBalanced(self, s: str) -> int:
        def calc1(s: str) -> int:
            res = 0
            i, n = 0, len(s)
            while i < n:
                j = i + 1
                while j < n and s[j] == s[i]:
                    j += 1
                res = max(res, j - i)
                i = j
            return res

        def calc2(s: str, a: str, b: str) -> int:
            res = 0
            i, n = 0, len(s)
            while i < n:
                while i < n and s[i] not in (a, b):
                    i += 1
                pos = {0: i - 1}
                d = 0
                while i < n and s[i] in (a, b):
                    d += 1 if s[i] == a else -1
                    if d in pos:
                        res = max(res, i - pos[d])
                    else:
                        pos[d] = i
                    i += 1
            return res

        def calc3(s: str) -> int:
            pos = {(0, 0): -1}
            cnt = Counter()
            res = 0
            for i, c in enumerate(s):
                cnt[c] += 1
                k = (cnt["a"] - cnt["b"], cnt["b"] - cnt["c"])
                if k in pos:
                    res = max(res, i - pos[k])
                else:
                    pos[k] = i
            return res

        x = calc1(s)
        y = max(calc2(s, "a", "b"), calc2(s, "b", "c"), calc2(s, "a", "c"))
        z = calc3(s)
        return max(x, y, z)

 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution {
    public int longestBalanced(String s) {
        char[] cs = s.toCharArray();
        int x = calc1(cs);
        int y = Math.max(calc2(cs, 'a', 'b'), Math.max(calc2(cs, 'b', 'c'), calc2(cs, 'a', 'c')));
        int z = calc3(cs);
        return Math.max(x, Math.max(y, z));
    }

    private int calc1(char[] s) {
        int res = 0;
        int i = 0, n = s.length;
        while (i < n) {
            int j = i + 1;
            while (j < n && s[j] == s[i]) {
                j++;
            }
            res = Math.max(res, j - i);
            i = j;
        }
        return res;
    }

    private int calc2(char[] s, char a, char b) {
        int res = 0;
        int i = 0, n = s.length;
        while (i < n) {
            while (i < n && s[i] != a && s[i] != b) {
                i++;
            }
            Map<Integer, Integer> pos = new HashMap<>();
            pos.put(0, i - 1);
            int d = 0;
            while (i < n && (s[i] == a || s[i] == b)) {
                d += (s[i] == a) ? 1 : -1;
                Integer prev = pos.get(d);
                if (prev != null) {
                    res = Math.max(res, i - prev);
                } else {
                    pos.put(d, i);
                }
                i++;
            }
        }
        return res;
    }

    private int calc3(char[] s) {
        Map<Long, Integer> pos = new HashMap<>();
        pos.put(f(0, 0), -1);

        int[] cnt = new int[3];
        int res = 0;

        for (int i = 0; i < s.length; i++) {
            char c = s[i];
            ++cnt[c - 'a'];
            int x = cnt[0] - cnt[1];
            int y = cnt[1] - cnt[2];
            long k = f(x, y);

            Integer prev = pos.get(k);
            if (prev != null) {
                res = Math.max(res, i - prev);
            } else {
                pos.put(k, i);
            }
        }
        return res;
    }

    private long f(int x, int y) {
        return (x + 100000) << 20 | (y + 100000);
    }
}

 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution {
public:
    int longestBalanced(string s) {
        int x = calc1(s);
        int y = max({calc2(s, 'a', 'b'), calc2(s, 'b', 'c'), calc2(s, 'a', 'c')});
        int z = calc3(s);
        return max({x, y, z});
    }

private:
    int calc1(const string& s) {
        int res = 0;
        int i = 0, n = s.size();
        while (i < n) {
            int j = i + 1;
            while (j < n && s[j] == s[i]) {
                ++j;
            }
            res = max(res, j - i);
            i = j;
        }
        return res;
    }

    int calc2(const string& s, char a, char b) {
        int res = 0;
        int i = 0, n = s.size();
        while (i < n) {
            while (i < n && s[i] != a && s[i] != b) {
                ++i;
            }

            unordered_map<int, int> pos;
            pos[0] = i - 1;

            int d = 0;
            while (i < n && (s[i] == a || s[i] == b)) {
                d += (s[i] == a) ? 1 : -1;
                auto it = pos.find(d);
                if (it != pos.end()) {
                    res = max(res, i - it->second);
                } else {
                    pos[d] = i;
                }
                i++;
            }
        }
        return res;
    }

    static long long f(int x, int y) {
        return ((long long) (x + 100000) << 20) | (long long) (y + 100000);
    }

    int calc3(const string& s) {
        unordered_map<long long, int> pos;
        pos[f(0, 0)] = -1;

        int cnt[3] = {0, 0, 0};
        int res = 0;

        for (int i = 0; i < (int) s.size(); i++) {
            char c = s[i];
            ++cnt[c - 'a'];
            int x = cnt[0] - cnt[1];
            int y = cnt[1] - cnt[2];
            long long k = f(x, y);

            auto it = pos.find(k);
            if (it != pos.end()) {
                res = max(res, i - it->second);
            } else {
                pos[k] = i;
            }
        }
        return res;
    }
};

 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
func longestBalanced(s string) int {
    x := calc1(s)
    y := max(calc2(s, 'a', 'b'), calc2(s, 'b', 'c'), calc2(s, 'a', 'c'))
    z := calc3(s)
    return max(x, max(y, z))
}

func calc1(s string) int {
    res := 0
    n := len(s)
    i := 0
    for i < n {
        j := i + 1
        for j < n && s[j] == s[i] {
            j++
        }
        if j-i > res {
            res = j - i
        }
        i = j
    }
    return res
}

func calc2(s string, a, b byte) int {
    res := 0
    n := len(s)
    i := 0
    for i < n {
        for i < n && s[i] != a && s[i] != b {
            i++
        }
        pos := map[int]int{0: i - 1}
        d := 0
        for i < n && (s[i] == a || s[i] == b) {
            if s[i] == a {
                d++
            } else {
                d--
            }
            if prev, ok := pos[d]; ok {
                if i-prev > res {
                    res = i - prev
                }
            } else {
                pos[d] = i
            }
            i++
        }
    }
    return res
}

type key struct {
    x, y int
}

func calc3(s string) int {
    pos := make(map[key]int)
    pos[key{0, 0}] = -1

    cnt := [3]int{}
    res := 0

    for i := 0; i < len(s); i++ {
        c := s[i]
        cnt[c-'a']++
        x := cnt[0] - cnt[1]
        y := cnt[1] - cnt[2]
        k := key{x, y}

        if j, ok := pos[k]; ok {
            if i-j > res {
                res = i - j
            }
        } else {
            pos[k] = i
        }
    }
    return res
}

 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
function longestBalanced(s: string): number {
    const x = calc1(s);
    const y = Math.max(calc2(s, 'a', 'b'), calc2(s, 'b', 'c'), calc2(s, 'a', 'c'));
    const z = calc3(s);
    return Math.max(x, y, z);
}

function calc1(s: string): number {
    let res = 0;
    const n = s.length;
    let i = 0;
    while (i < n) {
        let j = i + 1;
        while (j < n && s[j] === s[i]) j++;
        res = Math.max(res, j - i);
        i = j;
    }
    return res;
}

function calc2(s: string, a: string, b: string): number {
    let res = 0;
    const n = s.length;
    let i = 0;

    while (i < n) {
        while (i < n && s[i] !== a && s[i] !== b) i++;

        const pos = new Map<number, number>();
        pos.set(0, i - 1);

        let d = 0;
        while (i < n && (s[i] === a || s[i] === b)) {
            d += s[i] === a ? 1 : -1;

            const prev = pos.get(d);
            if (prev !== undefined) {
                res = Math.max(res, i - prev);
            } else {
                pos.set(d, i);
            }
            i++;
        }
    }
    return res;
}

function calc3(s: string): number {
    const pos = new Map<string, number>();
    pos.set(key(0, 0), -1);

    const cnt = [0, 0, 0];
    let res = 0;

    for (let i = 0; i < s.length; i++) {
        const c = s.charCodeAt(i) - 97;
        cnt[c]++;

        const x = cnt[0] - cnt[1];
        const y = cnt[1] - cnt[2];
        const k = key(x, y);

        const prev = pos.get(k);
        if (prev !== undefined) {
            res = Math.max(res, i - prev);
        } else {
            pos.set(k, i);
        }
    }
    return res;
}

function key(x: number, y: number): string {
    return x + '#' + y;
}

 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
use std::collections::HashMap;

impl Solution {
    pub fn longest_balanced(s: String) -> i32 {
        let x = Self::calc1(&s);
        let y = Self::calc2(&s, 'a', 'b')
            .max(Self::calc2(&s, 'b', 'c'))
            .max(Self::calc2(&s, 'a', 'c'));
        let z = Self::calc3(&s);
        x.max(y).max(z)
    }

    fn calc1(s: &str) -> i32 {
        let bytes = s.as_bytes();
        let mut res = 0i32;
        let mut i = 0usize;
        let n = bytes.len();

        while i < n {
            let mut j = i + 1;
            while j < n && bytes[j] == bytes[i] {
                j += 1;
            }
            res = res.max((j - i) as i32);
            i = j;
        }
        res
    }

    fn calc2(s: &str, a: char, b: char) -> i32 {
        let bytes = s.as_bytes();
        let a = a as u8;
        let b = b as u8;

        let mut res = 0i32;
        let mut i = 0usize;
        let n = bytes.len();

        while i < n {
            while i < n && bytes[i] != a && bytes[i] != b {
                i += 1;
            }

            let mut pos: HashMap<i32, i32> = HashMap::new();
            pos.insert(0, i as i32 - 1);

            let mut d = 0i32;
            while i < n && (bytes[i] == a || bytes[i] == b) {
                if bytes[i] == a {
                    d += 1;
                } else {
                    d -= 1;
                }

                if let Some(&pre) = pos.get(&d) {
                    res = res.max(i as i32 - pre);
                } else {
                    pos.insert(d, i as i32);
                }
                i += 1;
            }
        }

        res
    }

    fn f(x: i32, y: i32) -> i64 {
        (((x + 100000) as i64) << 20) | ((y + 100000) as i64)
    }

    fn calc3(s: &str) -> i32 {
        let mut pos: HashMap<i64, i32> = HashMap::new();
        pos.insert(Self::f(0, 0), -1);

        let mut cnt = [0i32; 3];
        let mut res = 0i32;

        for (i, c) in s.bytes().enumerate() {
            cnt[(c - b'a') as usize] += 1;

            let x = cnt[0] - cnt[1];
            let y = cnt[1] - cnt[2];
            let k = Self::f(x, y);

            if let Some(&pre) = pos.get(&k) {
                res = res.max(i as i32 - pre);
            } else {
                pos.insert(k, i as i32);
            }
        }

        res
    }
}

Comments