FastPrep
Problem · String

Is Convertible Data

Learn this problem
● MediumIBMINTERNOA
See IBM hiring insights

Problem statement

Given a dataset of strings containing only parentheses, characters '(' and ')', the data represented by the string is valid if it is a balanced bracket sequence. One adjustment to the string can be made: at most one bracket can be moved from its original place to any other position in the string. The task is to determine whether, for each string, it is possible to balanced the bracket sequence in 1 move or less. Return an array of the size of the dataset, where the j^th integer is 1 if the string can be converted into a balanced string, and 0 otherwise.

Note: A string s is a balanced bracket sequence if:

  • s is empty.
  • s is equal to "(t)", where t is a balanced bracket sequence.
  • s is equal to t_1t_2, i.e. concatenation of t_1 and t_2 where t_1 and t_2 are balanced bracket sequences.

    • Function

    isConvertibleData(dataset: String[]) → int[]

    Complete the function isConvertibleData in the editor.

    isConvertibleData takes the following parameter(s):

    1. String[] dataset: the dataset where each string contains characters ')' and '('

    Returns

    int[]: an array of integers, where the j^th integer is 1 if the corresponding string can be transformed into a balanced bracket sequence and 0 otherwise

    ૮꒰ ˶• ༝ •˶꒱ა ♡ Credit to Charlotte

    Examples

    Example 1

    dataset = [")(", "(()", "()"]return = [1, 0, 1]
    For the first string ")(", applying the operation to move the first bracket to the end results in "()", which is a balanced bracket sequence. For the second string "(()", it is impossible to convert it into a balanced bracket sequence. For the third string "()", it is already a balanced bracket sequence. Hence, the answer is [1, 0, 1].

    Constraints

    • 1 ≤ n ≤ 2 * 10^5
    • 1 ≤ |dataset[i]| ≤ 2 * 10^5
    • n ≤ Σ|dataset[i]| ≤ 2 * 10^5
    • It is guaranteed that each string dataset[i] consists of characters '(' and ')' only

    More IBM problems

    drafts saved locally
    public int[] isConvertibleData(String[] dataset) {
  // write your code here
}
    dataset[")(", "(()", "()"]
    expected[1, 0, 1]
    checking account