Skip to main content Link Menu Expand (external link) Document Search Copy Copied
Syntax Savvy

Java Coding Challenge: Longest Valid Parentheses Substring

Coding Pirate

Introduction

In this Java coding challenge, the task is to find the longest valid parentheses substring in a given string consisting of only ‘(‘ and ‘)’ characters. A valid parentheses substring is a string formed by an appropriate pairing of opening and closing parentheses. The challenge requires implementing an efficient algorithm that can identify the longest continuous sequence of correctly paired parentheses within the input string. This problem is commonly encountered in programming contests, job interviews, and as a part of algorithm courses, due to its relevance in testing a candidate’s understanding of data structures, problem-solving skills, and the ability to write efficient and clean code.

Test Cases

These test cases cover a variety of scenarios, such as empty strings, single characters, simple valid and invalid parentheses combinations, nested valid parentheses, and multiple valid and invalid segments. This diverse set of test cases will help you ensure that your longestValidParentheses method works correctly for a wide range of inputs.

Here are 15 different JUnit test cases for the longestValidParentheses method:

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

public class LongestValidParenthesesTest {

    @Test
    public void testEmptyString() {
        assertEquals(0, LongestValidParentheses.longestValidParentheses(""));
    }

    @Test
    public void testSingleCharacter() {
        assertEquals(0, LongestValidParentheses.longestValidParentheses("("));
        assertEquals(0, LongestValidParentheses.longestValidParentheses(")"));
    }

    @Test
    public void testSimpleValid() {
        assertEquals(2, LongestValidParentheses.longestValidParentheses("()"));
    }

    @Test
    public void testSimpleInvalid() {
        assertEquals(0, LongestValidParentheses.longestValidParentheses(")("));
    }

    @Test
    public void testNestedValid() {
        assertEquals(6, LongestValidParentheses.longestValidParentheses("(()())"));
    }

    @Test
    public void testTwoValidSegments() {
        assertEquals(4, LongestValidParentheses.longestValidParentheses("(())()"));
    }

    @Test
    public void testTwoValidSegmentsSeparated() {
        assertEquals(4, LongestValidParentheses.longestValidParentheses("(())(())"));
    }

    @Test
    public void testOnlyOpeningParentheses() {
        assertEquals(0, LongestValidParentheses.longestValidParentheses("((((((("));
    }

    @Test
    public void testOnlyClosingParentheses() {
        assertEquals(0, LongestValidParentheses.longestValidParentheses(")))))))"));
    }

    @Test
    public void testValidAndInvalidMixed1() {
        assertEquals(6, LongestValidParentheses.longestValidParentheses(")()())"));
    }

    @Test
    public void testValidAndInvalidMixed2() {
        assertEquals(4, LongestValidParentheses.longestValidParentheses("))()()"));
    }

    @Test
    public void testValidAndInvalidMixed3() {
        assertEquals(2, LongestValidParentheses.longestValidParentheses(")(())(("));
    }

    @Test
    public void testValidAndInvalidMixed4() {
        assertEquals(4, LongestValidParentheses.longestValidParentheses(")()((())"));
    }

    @Test
    public void testAlternatingParentheses() {
        assertEquals(6, LongestValidParentheses.longestValidParentheses("((((()))))"));
    }

    @Test
    public void testRandomParentheses() {
        assertEquals(2, LongestValidParentheses.longestValidParentheses("()((())()("));
    }
}

Solution

To solve this coding challenge, we will use a stack data structure to keep track of the indices of the opening parentheses. This way, we can effectively find the length of the longest valid parentheses substring. Here’s a step-by-step solution with code snippets:

Step 1: Import necessary packages

In the first step of solving the coding challenge, we import the necessary packages required for the implementation. In this particular challenge, we need to import the Stack class from the java.util package. The Stack class provides a built-in data structure that allows us to store and manipulate a collection of elements in a last-in, first-out (LIFO) order. The Stack class provides methods such as push(), pop(), peek(), and isEmpty() which we will use throughout the solution to handle opening and closing parentheses efficiently.

Here’s the code snippet for importing the necessary package:

import java.util.Stack;

By importing the Stack class, we can create and use stack objects in our implementation to keep track of the indices of the opening parentheses, making it easier to identify and calculate the length of the longest valid parentheses substring in the input string.

Step 2: Create a longestValidParentheses method

In this step, we define a method named longestValidParentheses that will take a string s as its input argument and return an integer representing the length of the longest valid parentheses substring. This method will encapsulate the main logic to solve the given problem.

By creating a separate method for this functionality, we ensure that our code is modular, easy to understand, and reusable. In the next steps, we will implement the algorithm within this method to solve the challenge effectively.

public static int longestValidParentheses(String s) {
    // Implement the method
}

Step 3: Initialize a Stack object and a variable to store the starting index

In step 3, we initialize two important variables to assist in our algorithm implementation. The first variable is a Stack object named stack, which will be used to store the indices of the opening parentheses encountered in the input string. The Stack data structure is chosen due to its Last-In-First-Out (LIFO) property, which allows us to keep track of the most recent opening parentheses and efficiently match them with corresponding closing parentheses.

The second variable we initialize is an integer called start. This variable is used to keep track of the starting index of the substring that we are currently evaluating. By maintaining this starting index, we can easily calculate the length of valid parentheses substrings as we traverse through the input string.

Additionally, we initialize a variable named maxLength and set its initial value to 0. This variable will be used to store the length of the longest valid parentheses substring found during the execution of our algorithm.

Stack<Integer> stack = new Stack<>();
int start = 0;
int maxLength = 0;

Step 4: Loop through the characters in the input string

In this step, we will iterate through each character of the input string using a for loop. The loop will start with the index i set to 0, and it will continue until i reaches the length of the input string. For each iteration, we will store the character at the current index i in a variable c.

This allows us to examine and process each character in the input string one by one to determine if it’s an opening or closing parenthesis and handle the related logic accordingly.

for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    // Implement the conditions inside the loop
}

By looping through the characters in the input string, we can efficiently analyze the given string and update the stack, starting index, and maxLength variables accordingly. This helps us eventually identify the longest valid parentheses substring in the given input.

Step 5: Check if the current character is an opening parenthesis

In step 5 of the solution, the algorithm checks if the current character is an opening parenthesis. This is an important step because it allows the program to keep track of the opening parentheses encountered while iterating through the input string.

When an opening parenthesis is found, the current index i is pushed onto the stack. Storing the index on the stack helps maintain the order of the opening parentheses encountered in the string. This way, the program can later determine whether the parentheses are correctly paired when it encounters a closing parenthesis.

This step is essential for identifying valid parentheses substrings in the input string and updating the longest valid parentheses substring length accordingly.

if (c == '(') {
    stack.push(i);
}

Step 6: If it’s a closing parenthesis, pop the opening parenthesis index from the stack and update the maxLength

If the current character is a closing parenthesis, pop the opening parenthesis index from the stack and update the maxLength. This is done in the following sub-steps:

a. If the stack is empty, that means there is no matching opening parenthesis for the current closing parenthesis. In this case, update the start variable to i + 1, as the valid substring search should restart after the unmatched closing parenthesis.

if (stack.isEmpty()) {
    start = i + 1;
}

b. If the stack is not empty, pop the index of the opening parenthesis from the stack. Then, update the maxLength variable by comparing its current value with the length of the valid parentheses substring that ends at the current index i. If the stack is empty after the pop operation, calculate the length as i - start + 1. If the stack is still not empty, calculate the length as i - stack.peek(). In both cases, use the Math.max function to keep the maximum length found so far.

else {
    stack.pop();
    maxLength = stack.isEmpty() ? Math.max(maxLength, i - start + 1) : Math.max(maxLength, i - stack.peek());
}

By following these steps, we ensure that we keep track of the longest valid parentheses substring found in the input string as we iterate through its characters.

Step 7: Return the maxLength value

After iterating through the entire input string, the maxLength variable holds the length of the longest valid parentheses substring found during the process.

By returning this value from the longestValidParentheses method, we provide the final result of the challenge. This step completes the implementation, allowing us to use the method for different input strings and obtain the desired output in each case.

return maxLength;

Complete Solution

Here’s the complete solution:

import java.util.Stack;

public class LongestValidParentheses {

    public static void main(String[] args) {
        String input = "(()())";
        System.out.println(longestValidParentheses(input)); // Output: 6
    }

    public static int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        int start = 0;
        int maxLength = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '(') {
                stack.push(i);
            } else {
                if (stack.isEmpty()) {
                    start = i + 1;
                } else {
                    stack.pop();
                    maxLength = stack.isEmpty() ? Math.max(maxLength, i - start + 1) : Math.max(maxLength, i - stack.peek());
                }
            }
        }

        return maxLength;
    }
}

Time Complexity (Big-O)

The time complexity of the given solution to find the longest valid parentheses substring in a given string is O(n), where n is the length of the input string. This linear time complexity is due to the single for-loop that iterates through each character in the input string. The loop processes each character exactly once, with each operation inside the loop having a constant time complexity.

The space complexity of the solution is also O(n) because, in the worst-case scenario, the stack could store all the opening parentheses in the input string. For example, consider a string that consists of only opening parentheses, like “(((((“. In this case, the stack would store the indices of all opening parentheses, leading to a space complexity of O(n).

In summary, the given solution has a time complexity of O(n) and a space complexity of O(n).

In conclusion, we have successfully implemented a Java solution to find the longest valid parentheses substring in a given string using a stack data structure. This coding challenge is an excellent way to practice problem-solving skills, algorithm design, and the use of efficient data structures. It demonstrates the importance of understanding the problem’s requirements and breaking it down into smaller, man

By following this step-by-step solution, you can further deepen your knowledge of Java programming, data structures, and algorithmic thinking. Feel free to experiment with different input cases, optimize the solution further, or explore alternative approaches to expand your skillset and gain confidence in tackling similar challenges in the future.