Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • Creating the Zuma game

    You’ve decided to create the game Zuma. You’re now working on the part that removes segments of balls having the same color when the segments hit each other. So, having a list of balls with different colors, the player shoots with a ball of some color to a specific position in that line. If there are more than 2 balls with the same color at that segment (including the ball shot by the player), that segment of balls disappears, and the balls surrounding it fill the gap.
    notion image
    If 2 or more balls colliding have the same color, that segment of balls with the same color disappears as well. This process continues until the colliding segments have different colors or there are no balls left.

    Input

    The first line of the input contains a single string b (1 ≤ |b| ≤ ) representing the balls in the line. The colors of the balls are represented as lowercase Latin letters (y for yellow, b for blue, r for red, etc).
    The next line contains the index at which the user shoots a ball i (1 ≤ i ≤ |b|) and the color of the ball c (lowercase Latin letter).

    Output

    The programs should print the resulting sequence of balls.

    Examples

    Input
    Output
    rrryyrrb 4 y
    b
    rgbbrg 3 b
    rgrg
    ggrrrbbb 1 g
    rrrbbb
    gbyw 1 y
    ygbyw

    Explanation

    1. rrryyrrb → rrryyrrb → rrrrrb → b
    1. rgbbrg → rgbbrg → rgrg
    1. ggrrrbbb → ggrrrbbb → rrrbbb (no collision between segments after this)
    1. gbyw → gbyw → ygbyw (the colors do not match ⇒ insert the ball at the index at which it was shot)
     

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue