CodeSignal Arcade – reverseInParentheses

4 months ago

ngocnb

2 minutes

Contents

1 Problem
2 Solution
- 2.1 Idea
- 2.2 Code

Problem

Write a function that reverses characters in (possibly nested) parentheses in the input string.

Input strings will always be well-formed with matching ()s.

Example

For inputString = "(bar)", the output should be
solution(inputString) = "rab";
For inputString = "foo(bar)baz", the output should be
solution(inputString) = "foorabbaz";
For inputString = "foo(bar)baz(blim)", the output should be
solution(inputString) = "foorabbazmilb";
For inputString = "foo(bar(baz))blim", the output should be
solution(inputString) = "foobazrabblim".
Because "foo(bar(baz))blim" becomes "foo(barzab)blim" and then "foobazrabblim".

Solution

Idea

My idea is search and get the index of all the pairs of parenthesis (start = open parenthesis, stop = close parenthesis) in the inputString. After that, I loop through the pairs and swap the characters between the start and stop index.

There’s a problem with the swapping feature. We need to check the character and ignore it if it’s the parenthesis. If it’s the start postion, plus 1. If it’s the end position, minus 1. Then continue the loop.

Code

function solution(inputString) {
    // get all the open and close parentheses pairs
    let pairs = [];
    for (let i = 0; i < inputString.length; i++) {
        let char = inputString[i];
        if (char === "(") {
            pairs.push({start: i, stop: 0});
        }
        
        if (char === ")") {
            for (let j = pairs.length - 1; j >= 0; j--) {
                if (pairs[j].stop === 0) {
                    pairs[j].stop = i;
                    break;
                }
            }
        }
    }
    
    // swap characters between start and end position
    for (let i = pairs.length - 1; i >= 0; i--) {
        const pair = pairs[i];
        
        inputString = swapCharactersInString(inputString, pair.start + 1, pair.stop - 1);
        console.log("result", inputString);
    }
    
    // remove parenthesis
    inputString = inputString.replace(/[()]/g, '');
    
    return inputString;
}

function swapCharactersInString(str, start, end) {
    let arr = [...str];
    while (start < end) {
        if (arr[start] === "(" || arr[start] === ")") {
            start += 1;
            continue;
        }
        if (arr[end] === ")" || arr[end] === "(") {
            end -= 1;
            continue;
        }
        [arr[start], arr[end]] = [arr[end], arr[start]];
        start += 1;
        end -= 1;
    }
    return arr.join("");
}

#algorithm #codesignal #javascript