Ctrl K

Bead String Without Twins

Medium
Beads are threaded on a string in a row. Bead i has the colour beads[i] (a letter), and taking it off the string costs effort[i] seconds. You want no two neighbouring beads to share a colour. To get there you may remove any beads; the remaining ones close up, so the beads on either side of a removed one become neighbours. Return the smallest total time needed to achieve this.
Example 1
beads="rggbg", effort=[2, 5, 3, 1, 4] → 3

Two g beads sit side by side at positions 1 and 2. Removing the second one is cheaper: 3 seconds.

Example 2
beads="bbbab", effort=[4, 1, 6, 2, 2] → 5

The string starts with three b beads in a row: keep the costliest one (6) and remove the others for 4 + 1 = 5.

Example 3
beads="abc", effort=[7, 7, 7] → 0

No two neighbours share a colour, so nothing has to go.

Constraints
  • 1 ≤ len(beads) ≤ 10⁵
  • len(effort) = len(beads)
  • 1 ≤ effort[i] ≤ 10⁴
  • beads consists of lowercase English letters
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsWord From a Prefix Table HardAlternating Team Picks EasyFewest Jumps to the End MediumReach the Last Cell MediumAs Many Trades as You Like Medium
loading Python…
Input
beads="rggbg", effort=[2, 5, 3, 1, 4]
Expected
3

Run checks the first 3 tests in your browser. Submit checks all 81 tests on the server, hidden ones included.