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

 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;
}

Comments