URL

https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/description/?envType=daily-question&envId=2024-04-06

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/challenge/202404/minimum_remove_to_make_valid_parentheses/main.fsx

open System

let minRemoveToMakeValid (s: string) : string =
    let rec invalidParentheses cs q =
        match cs with
        | [] -> q |> List.map fst |> List.rev |> Set.ofList
        | (i, h) :: t ->
            match h with
            | '(' -> invalidParentheses t ((i, h) :: q)
            | ')' ->
                match q with
                | [] -> invalidParentheses t ((i, h) :: q)
                | (_, h') :: t' ->
                    if h' = '(' then
                        invalidParentheses t t'
                    else
                        invalidParentheses t ((i, h) :: q)
            | _ -> invalidParentheses t q

    let cs = Seq.toList s |> List.indexed
    let invalidIndexes = invalidParentheses cs []

    s
    |> Seq.indexed
    |> Seq.filter (fun (i, _) -> not <| Set.contains i invalidIndexes)
    |> Seq.map snd
    |> String.Concat