Delete AB

AtCoder

IDagc074_e

Time4000ms

Memory256MB

Difficulty—

For a string $X = X_1X_2\dots X_{|X|}$ and positive integers $l,r~(1 \leq l \leq r \leq |X|)$, let $X_{l,r} = X_l X_{l+1}\dots X_r$. You are given a string $S=S_1S_2\dots S_{|S|}$ consisting of `A` and `B`. You are given $Q$ queries. For each query, answer the following question: * Starting from the state $T = S_{l,r}$, find the minimum possible length of a palindrome that can be obtained by performing the operation "choose one occurrence of `AB` that appears as a contiguous substring in $T$ and delete it" zero or more times. If no palindrome can be obtained regardless of how the operation is performed, output `-1`. ## Constraints * $1 \leq |S| \leq 4 \times 10^5$ * $1 \leq Q \leq 5 \times 10^4$ * $1 \leq l \leq r \leq |S|$ * $S$ is a string consisting of `A` and `B`. * $Q,l,r$ are integers. ## Input The input is given from Standard Input in the following format: $S$ $Q$ $\mathrm{Query}_1$ $\mathrm{Query}_2$ $\vdots$ $\mathrm{Query}_Q$ $\mathrm{Query}_q$ represents the $q$\-th query and is given in the following format: $l$ $r$ [samples]

Samples

Input #1

ABBABB
5
1 6
4 5
3 5
2 3
3 4

Output #1

2
0
1
2
-1

For the first, second, and third queries, by performing the operation as follows, you can obtain a palindrome with the minimum length among those obtained by the operation.

*   `ABBABB` $\rightarrow$ `ABBB` $\rightarrow$ `BB`
*   `AB` $\rightarrow$ (empty string)
*   `BAB` $\rightarrow$ `B`

API Response (JSON)

{
  "problem": {
    "name": "Delete AB",
    "description": {
      "content": "For a string $X = X_1X_2\\dots X_{|X|}$ and positive integers $l,r~(1 \\leq l \\leq r \\leq |X|)$, let $X_{l,r} = X_l X_{l+1}\\dots X_r$. You are given a string $S=S_1S_2\\dots S_{|S|}$ consisting of `A` an",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc074_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For a string $X = X_1X_2\\dots X_{|X|}$ and positive integers $l,r~(1 \\leq l \\leq r \\leq |X|)$, let $X_{l,r} = X_l X_{l+1}\\dots X_r$.\nYou are given a string $S=S_1S_2\\dots S_{|S|}$ consisting of `A` an...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments