F. Balloons (A)

Codeforces

IDCF10140F

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

There are N balloons linked together in a line. Each balloon is either red, green, or blue. Mr. Light wants to get exactly one balloon of each color (exactly one red balloon, one green balloon, and one blue balloon) - no more or less. Find the minimum number of cuts he has to make to achieve this. This picture illustrates the first sample test case: "RRGRGRRB". Each letter represents one of the three colors. After making these cuts, Mr. Light will get the two balloons "GR" and the last balloon "B". Note that the three balloons Mr. Light will get don't have to be disconnected, and it is only allowed to cut the rope that links the balloons together. The input contains a string S (3 ≤ |S| ≤ 2 × 105), representing the balloons in the line. Each letter is either 'R', 'G', or 'B' and represents the color of that balloon. It is guaranteed that for each color, there exists at least one balloon with that color. Print the minimum number of cuts on a single line. ## Input The input contains a string S (3 ≤ |S| ≤ 2 × 105), representing the balloons in the line. Each letter is either 'R', 'G', or 'B' and represents the color of that balloon.It is guaranteed that for each color, there exists at least one balloon with that color. ## Output Print the minimum number of cuts on a single line. [samples]

**Definitions** Let $ S = s_1 s_2 \dots s_n $ be a string of length $ n $, where $ s_i \in \{R, G, B\} $, and $ 3 \leq n \leq 2 \times 10^5 $. Let $ C = \{R, G, B\} $ denote the set of colors. **Constraints** For each color $ c \in C $, there exists at least one index $ i $ such that $ s_i = c $. **Objective** Find the minimum number of cuts required to extract exactly one balloon of each color (one $ R $, one $ G $, one $ B $), where a cut separates adjacent balloons. The selected balloons must form a contiguous substring (i.e., no gaps), and the number of cuts equals the number of adjacent pairs broken to isolate this substring. Equivalently, find the minimum length of a contiguous substring of $ S $ that contains at least one occurrence of each color $ R, G, B $. Then, the minimum number of cuts is: $$ \text{min\_length} - 1 $$

API Response (JSON)

{
  "problem": {
    "name": "F. Balloons (A)",
    "description": {
      "content": "There are N balloons linked together in a line. Each balloon is either red, green, or blue. Mr. Light wants to get exactly one balloon of each color (exactly one red balloon, one green balloon, and on",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10140F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are N balloons linked together in a line. Each balloon is either red, green, or blue. Mr. Light wants to get exactly one balloon of each color (exactly one red balloon, one green balloon, and on...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S = s_1 s_2 \\dots s_n $ be a string of length $ n $, where $ s_i \\in \\{R, G, B\\} $, and $ 3 \\leq n \\leq 2 \\times 10^5 $.  \nLet $ C = \\{R, G, B\\} $ denote the set of colors.  \n\n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments