Skip to content

3777. Minimum Deletions to Make Alternating Substring

Description

You are given a string s of length n consisting only of the characters 'A' and 'B'.

You are also given a 2D integer array queries of length q, where each queries[i] is one of the following:

  • [1, j]: Flip the character at index j of s i.e. 'A' changes to 'B' (and vice versa). This operation mutates s and affects subsequent queries.
  • [2, l, r]: Compute the minimum number of character deletions required to make the substring s[l..r] alternating. This operation does not modify s; the length of s remains n.

A substring is alternating if no two adjacent characters are equal. A substring of length 1 is always alternating.

Return an integer array answer, where answer[i] is the result of the ith query of type [2, l, r].

Β 

Example 1:

Input: s = "ABA", queries = [[2,1,2],[1,1],[2,0,2]]

Output: [0,2]

Explanation:

i queries[i] j l r s before query s[l..r] Result Answer
0 [2, 1, 2] - 1 2 "ABA" "BA" Already alternating 0
1 [1, 1] 1 - - "ABA" - Flip s[1] from 'B' to 'A' -
2 [2, 0, 2] - 0 2 "AAA" "AAA" Delete any two 'A's to get "A" 2

Thus, the answer is [0, 2].

Example 2:

Input: s = "ABB", queries = [[2,0,2],[1,2],[2,0,2]]

Output: [1,0]

Explanation:

i queries[i] j l r s before query s[l..r] Result Answer
0 [2, 0, 2] - 0 2 "ABB" "ABB" Delete one 'B' to get "AB" 1
1 [1, 2] 2 - - "ABB" - Flip s[2] from 'B' to 'A' -
2 [2, 0, 2] - 0 2 "ABA" "ABA" Already alternating 0

Thus, the answer is [1, 0].

Example 3:

Input: s = "BABA", queries = [[2,0,3],[1,1],[2,1,3]]

Output: [0,1]

Explanation:

i queries[i] j l r s before query s[l..r] Result Answer
0 [2, 0, 3] - 0 3 "BABA" "BABA" Already alternating 0
1 [1, 1] 1 - - "BABA" - Flip s[1] from 'A' to 'B' -
2 [2, 1, 3] - 1 3 "BBBA" "BBA" Delete one 'B' to get "BA" 1

Thus, the answer is [0, 1].

Β 

Constraints:

  • 1 <= n == s.length <= 105
  • s[i] is either 'A' or 'B'.
  • 1 <= q == queries.length <= 105
  • queries[i].length == 2 or 3
    • queries[i] == [1, j] or,
    • queries[i] == [2, l, r]
    • 0 <= j <= n - 1
    • 0 <= l <= r <= n - 1

Solutions

Solution 1: Binary Indexed Tree

We can convert the string \(s\) into an array \(\textit{nums}\) of length \(n\), where \(\textit{nums}[0] = 0\), and for \(1 \leq i < n\), if \(s[i] = s[i-1]\), then \(\textit{nums}[i] = 1\), otherwise \(\textit{nums}[i] = 0\). This way \(\textit{nums}[i]\) represents whether there are adjacent and equal characters at index \(i\). Then calculating the minimum number of character deletions required to make the substring \(s[l..r]\) an alternating string in the interval \([l, r]\) is equivalent to calculating the sum of elements in the \(\textit{nums}\) array over the interval \([l+1, r]\).

To handle queries efficiently, we can use a Binary Indexed Tree to maintain the prefix sum of the \(\textit{nums}\) array. For queries of type \([1, j]\), we need to flip \(\textit{nums}[j]\) and \(\textit{nums}[j+1]\) (if \(j+1 < n\)), and update the Binary Indexed Tree. For queries of type \([2, l, r]\), we can quickly calculate the sum of elements over the interval \([l+1, r]\) through the Binary Indexed Tree.

The time complexity is \(O((n + q) \log n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the string \(s\), and \(q\) is the number of queries.

 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
class BinaryIndexedTree:
    __slots__ = "n", "c"

    def __init__(self, n: int):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x: int, delta: int) -> None:
        while x <= self.n:
            self.c[x] += delta
            x += x & -x

    def query(self, x: int) -> int:
        s = 0
        while x:
            s += self.c[x]
            x -= x & -x
        return s


class Solution:
    def minDeletions(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)
        nums = [0] * n
        bit = BinaryIndexedTree(n)
        for i in range(1, n):
            nums[i] = int(s[i] == s[i - 1])
            if nums[i]:
                bit.update(i + 1, 1)
        ans = []
        for q in queries:
            if q[0] == 1:
                j = q[1]
                delta = (nums[j] ^ 1) - nums[j]
                nums[j] ^= 1
                bit.update(j + 1, delta)
                if j + 1 < n:
                    delta = (nums[j + 1] ^ 1) - nums[j + 1]
                    nums[j + 1] ^= 1
                    bit.update(j + 2, delta)
            else:
                _, l, r = q
                ans.append(bit.query(r + 1) - bit.query(l + 1))
        return ans

 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
class BinaryIndexedTree {
    int n;
    int[] c;

    BinaryIndexedTree(int n) {
        this.n = n;
        this.c = new int[n + 1];
    }

    void update(int x, int delta) {
        while (x <= n) {
            c[x] += delta;
            x += x & -x;
        }
    }

    int query(int x) {
        int s = 0;
        while (x > 0) {
            s += c[x];
            x -= x & -x;
        }
        return s;
    }
}

class Solution {
    public int[] minDeletions(String s, int[][] queries) {
        int n = s.length();
        int[] nums = new int[n];
        BinaryIndexedTree bit = new BinaryIndexedTree(n);

        for (int i = 1; i < n; i++) {
            nums[i] = (s.charAt(i) == s.charAt(i - 1)) ? 1 : 0;
            if (nums[i] == 1) {
                bit.update(i + 1, 1);
            }
        }

        int cnt = 0;
        for (int[] q : queries) {
            if (q[0] == 2) {
                cnt++;
            }
        }

        int[] ans = new int[cnt];
        int idx = 0;

        for (int[] q : queries) {
            if (q[0] == 1) {
                int j = q[1];

                int delta = (nums[j] ^ 1) - nums[j];
                nums[j] ^= 1;
                bit.update(j + 1, delta);

                if (j + 1 < n) {
                    delta = (nums[j + 1] ^ 1) - nums[j + 1];
                    nums[j + 1] ^= 1;
                    bit.update(j + 2, delta);
                }
            } else {
                int l = q[1];
                int r = q[2];
                ans[idx++] = bit.query(r + 1) - bit.query(l + 1);
            }
        }
        return ans;
    }
}

 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
class BinaryIndexedTree {
public:
    int n;
    vector<int> c;

    BinaryIndexedTree(int n)
        : n(n)
        , c(n + 1, 0) {}

    void update(int x, int delta) {
        while (x <= n) {
            c[x] += delta;
            x += x & -x;
        }
    }

    int query(int x) {
        int s = 0;
        while (x > 0) {
            s += c[x];
            x -= x & -x;
        }
        return s;
    }
};

class Solution {
public:
    vector<int> minDeletions(string s, vector<vector<int>>& queries) {
        int n = s.size();
        vector<int> nums(n, 0);
        BinaryIndexedTree bit(n);

        for (int i = 1; i < n; i++) {
            nums[i] = (s[i] == s[i - 1]);
            if (nums[i]) {
                bit.update(i + 1, 1);
            }
        }

        vector<int> ans;

        for (auto& q : queries) {
            if (q[0] == 1) {
                int j = q[1];

                int delta = (nums[j] ^ 1) - nums[j];
                nums[j] ^= 1;
                bit.update(j + 1, delta);

                if (j + 1 < n) {
                    delta = (nums[j + 1] ^ 1) - nums[j + 1];
                    nums[j + 1] ^= 1;
                    bit.update(j + 2, delta);
                }
            } else {
                int l = q[1];
                int r = q[2];
                ans.push_back(bit.query(r + 1) - bit.query(l + 1));
            }
        }
        return ans;
    }
};

 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
type binaryIndexedTree struct {
    n int
    c []int
}

func newBinaryIndexedTree(n int) *binaryIndexedTree {
    return &binaryIndexedTree{
        n: n,
        c: make([]int, n+1),
    }
}

func (bit *binaryIndexedTree) update(x, delta int) {
    for x <= bit.n {
        bit.c[x] += delta
        x += x & -x
    }
}

func (bit *binaryIndexedTree) query(x int) int {
    s := 0
    for x > 0 {
        s += bit.c[x]
        x -= x & -x
    }
    return s
}

func minDeletions(s string, queries [][]int) []int {
    n := len(s)
    nums := make([]int, n)
    bit := newBinaryIndexedTree(n)

    for i := 1; i < n; i++ {
        if s[i] == s[i-1] {
            nums[i] = 1
            bit.update(i+1, 1)
        }
    }

    ans := make([]int, 0)

    for _, q := range queries {
        if q[0] == 1 {
            j := q[1]

            delta := (nums[j] ^ 1 - nums[j])
            nums[j] ^= 1
            bit.update(j+1, delta)

            if j+1 < n {
                delta = (nums[j+1] ^ 1 - nums[j+1])
                nums[j+1] ^= 1
                bit.update(j+2, delta)
            }
        } else {
            l, r := q[1], q[2]
            ans = append(ans, bit.query(r+1)-bit.query(l+1))
        }
    }

    return ans
}

 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
class BinaryIndexedTree {
    n: number;
    c: number[];

    constructor(n: number) {
        this.n = n;
        this.c = Array(n + 1).fill(0);
    }

    update(x: number, delta: number): void {
        while (x <= this.n) {
            this.c[x] += delta;
            x += x & -x;
        }
    }

    query(x: number): number {
        let s = 0;
        while (x > 0) {
            s += this.c[x];
            x -= x & -x;
        }
        return s;
    }
}

function minDeletions(s: string, queries: number[][]): number[] {
    const n = s.length;
    const nums: number[] = Array(n).fill(0);
    const bit = new BinaryIndexedTree(n);

    for (let i = 1; i < n; i++) {
        if (s[i] === s[i - 1]) {
            nums[i] = 1;
            bit.update(i + 1, 1);
        }
    }

    const ans: number[] = [];

    for (const q of queries) {
        if (q[0] === 1) {
            const j = q[1];

            let delta = (nums[j] ^ 1) - nums[j];
            nums[j] ^= 1;
            bit.update(j + 1, delta);

            if (j + 1 < n) {
                delta = (nums[j + 1] ^ 1) - nums[j + 1];
                nums[j + 1] ^= 1;
                bit.update(j + 2, delta);
            }
        } else {
            const l = q[1],
                r = q[2];
            ans.push(bit.query(r + 1) - bit.query(l + 1));
        }
    }

    return ans;
}

Comments