Multi-Threaded Parentheses Validator

Problem: Parallel Parentheses Validator

Description

You are given a string s of length N consisting only of the characters '(' and ')'. A parentheses string is considered valid if:

1. Every '(' has a matching ')' to its right.

2. No prefix of the string contains more ')' than '('.

Write a function:

boolean isValidParallel(String s, int P)

that determines whether s is valid, using P worker threads. Each thread can only read a disjoint substring of s.

Solution

1. Sequential Approach

private static boolean isValidSequential(String s) {
    int balance = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            balance++;
        } else {
            balance--;
        }
        if (balance < 0) return false;
    }
    return balance == 0;
}

What is working here

• Simple and straightforward

• O(N) time complexity

• O(1) space complexity

• Easy to understand and debug

Drawbacks

• Cannot utilize multiple threads

• Doesn't meet the problem requirements for parallel processing

• Would be slow for extremely large strings

2. Naive Parallel Approach (Problematic)

// This approach doesn't work - just for discussion
boolean isValidNaiveParallel(String s, int P) {
    ExecutorService executor = Executors.newFixedThreadPool(P);
    int segmentSize = s.length() / P;
    Future<Boolean>[] futures = new Future[P];
    
    for (int i = 0; i < P; i++) {
        final int start = i * segmentSize;
        final int end = (i == P-1) ? s.length() : start + segmentSize;
        
        futures[i] = executor.submit(() -> {
            return isValidSequential(s.substring(start, end));
        });
    }
    
    // Collect results
    for (Future<Boolean> future : futures) {
        if (!future.get()) return false;
    }
    return true;
}

Why this fails:

• Each segment is validated independently, but validity depends on the entire prefix

• A segment might be locally valid but globally invalid due to balance dependencies

• Example: "())(" split as "())" and "(" - both segments fail local validation, but the real issue is global

3. Better Parallel Approach (The Working Solution)

static class SegmentResult {
    final int netBalance;
    final int minBalance;
    
    SegmentResult(int net, int min) {
        this.netBalance = net;
        this.minBalance = min;
    }
}

public static boolean isValidParallel(String s, int P) {
    // ... thread pool setup
    
    // Each thread processes its segment
    Future<SegmentResult>[] futures = new Future[P];
    for (int i = 0; i < P; i++) {
        final int start = i * segmentSize;
        final int end = Math.min(start + segmentSize, n);
        futures[i] = executor.submit(() -> processSegment(s, start, end));
    }
    
    // Sequential combination
    int currentBalance = 0;
    int globalMinBalance = 0;
    
    for (int i = 0; i < P; i++) {
        SegmentResult result = futures[i].get();
        globalMinBalance = Math.min(globalMinBalance, currentBalance + result.minBalance);
        currentBalance += result.netBalance;
    }
    
    return globalMinBalance >= 0 && currentBalance == 0;
}

This solution is great, but but what if we have very large P.

Solution 4