Welcome to Subscribe On Youtube

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.

• Java
• C++
• Python
• Go
• TypeScript

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

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

• 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
  
  

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

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

All Problems

All Solutions