CodeSignal reverseParentheses Failing one case

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

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

• For inputString = "(bar)", the output should be reverseInParentheses(inputString) = "rab";

• For inputString = "foo(bar)baz", the output should be reverseInParentheses(inputString) = "foorabbaz";

• For inputString = "foo(bar(baz))blim", the output should be reverseInParentheses(inputString) = "foobazrabblim".

[input] string inputString

A string consisting of lowercase English letters and the characters ( and ). It is guaranteed that all parentheses in inputString form a regular bracket sequence.

Guaranteed constraints:

0 ≤ inputString.length ≤ 50.

[output] string

Return inputString, with all the characters that were in parentheses reversed.

My Solution

• Java Script

function reverseInParentheses(inputString) {
    let arr = inputString
    let start = arr.indexOf(')') < arr.lastIndexOf('(') ? arr.indexOf('(') : arr.lastIndexOf('(')
    let end = arr.indexOf(')')
    
    let temp = arr.substring(start + 1, end)
    if(start !== -1 && end !== -1){
        return reverseInParentheses(arr.substring(0, start) + 
        [...temp].reverse().join('') + 
        arr.substring(end + 1))
    }
    return arr
}

Problem

I am passing all cases except for final hidden case, no runtime or execution time limit error is being returned. So I am having trouble figuring out what scenario is causing the fail. I really want to use my own solution instead of copying the regex ones and in my mind this solution should work, perhaps a more experienced mind can show my folly. Thanks in advance.

Answer

The problem is that your calculation of start and end really don’t work. And there’s no simple fix to this problem.

The comment from Jonas Wilms suggests trying '((see)(you))'. For this test case, you will get start and end like this:

          0    5
          ((see)(you))
          ^    ^
start ----'    '---- end    

Note that the start and end are not an actual pair here. There’s another '(' in between.

You can fix this up by doing a more sophisticated calculation of these values, by iterating through the characters, updating start every time you hit a '(' and updating end when you hit a ')', then stopping.

That might look like this:

function reverseInParentheses(inputString) {
    let arr = inputString
    let i = 0, start = 0, end = -1
    while (end < start && i < arr.length) {
        if (arr[i] == '(') {start = i}
        if (arr[i] == ')') {end = i}
        i++
    }
   
    let temp = arr.substring(start + 1, end)
    if(start !== -1 && end !== -1){
        return reverseInParentheses(arr.substring(0, start) + 
        [...temp].reverse().join('') + 
        arr.substring(end + 1))
    }
    return arr
}

console .log (reverseInParentheses('(bar)'))
console .log (reverseInParentheses('foo(bar)baz'))
console .log (reverseInParentheses('foo(bar(baz))blim'))
console .log (reverseInParentheses('((see)(you))'))

I don’t particularly like this, combining the iteration to find the parentheses with recursion to keep reapplying the function until there are none left. It feels awkward.

---

There are other solutions, as you noted. One would be to use regular expressions. Note that the language of balanced parentheses is not a regular language, and hence cannot be captured by any one regular expression, but you can repeatedly apply regular expression operations in an iteration or a recursion to get this to work. Here is one version of that.

const rev = ([...cs]) => cs.reverse().join('')

const reverseInParentheses = (s) =>
  /(([^)]*))/ .test (s) 
    ? reverseInParentheses (s .replace(/(.*)(([^)]*))(.*)/, (_, a, b, c) => a + rev(b) + c)) 
    : s

console .log (reverseInParentheses('(bar)'))
console .log (reverseInParentheses('foo(bar)baz'))
console .log (reverseInParentheses('foo(bar(baz))blim'))
console .log (reverseInParentheses('((see)(you))'))

Briefly, this finds innermost pairs of parentheses, replaces them with the reversal of their content, then recurs on the result, bottoming out when there are no more pairs found.

This solution was thrown together, and there are probably better regular expressions operations available.

---

But I actually prefer a different approach altogether, treating the characters of the string as events for a simple state machine, with a stack of nested parenthesized substrings. Here is what I wrote:

const reverseInParentheses = ([c, ...cs], res = ['']) =>
  c == undefined 
    ? res [0]
  : c == '('
    ? reverseInParentheses (cs, [...res, ''])
  : c == ')'
    ? reverseInParentheses (cs, [...res.slice(0, -2), res[res.length - 2] + [...res[res.length - 1]].reverse().join('')])
  : reverseInParentheses (cs, [...res.slice(0, -1), res[res.length - 1] + c])

console .log (reverseInParentheses('(bar)'))
console .log (reverseInParentheses('foo(bar)baz'))
console .log (reverseInParentheses('foo(bar(baz))blim'))
console .log (reverseInParentheses('((see)(you))'))

We can examine the behavior by adding this as the first line of the body expression:

  console .log (`c: ${c ? `"${c}"` : '< >'}, cs: "${cs.join('')}", res: ["${res.join('", "')}"]`) ||

For '((see)(you))', we would get something like this:

curr (c)	remaining (cs)	stack (res)
“(“	“(see)(you))”	[“”]
“(“	“see)(you))”	[“”, “”]
“s”	“ee)(you))”	[“”, “”, “”]
“e”	“e)(you))”	[“”, “”, “s”]
“e”	“)(you))”	[“”, “”, “se”]
“)”	“(you))”	[“”, “”, “see”]
“(“	“you))”	[“”, “ees”]
“y”	“ou))”	[“”, “ees”, “”]
“o”	“u))”	[“”, “ees”, “y”]
“u”	“))”	[“”, “ees”, “yo”]
“)”	“)”	[“”, “ees”, “you”]
“)”	“”	[“”, “eesuoy”]
< >	< >	[“yousee”]

I choose to process this state machine recursively, because I prefer working with immutable data, not reassigning variables, etc. But this technique should work equally well with an iterative approach.