Fix max potholes

You are given a description of a two-lane road in which two strings, L1 and L2, respectively represent the first and the second lane, each lane consisting of N segments of equal length.

The K-th segment of the first lane is represented by L1[K] and the K-th segment of the second lane is represented by L2[K], where '.' denotes a smooth segment of road and 'x' denotes a segment containing potholes.

Cars can drive over segments with potholes, but it is rather uncomfortable. Therefore, a project to repair as many potholes as possible was submitted. At most one contiguous stretch of each lane may be repaired at a time. For the time of reparation, those stretches will be closed to traffic.

How many road segments with potholes can be repaired given that the road must be kept open (in other words, stretches of roadworks must not prevent travel from one end of the road to the other)?

Given two strings L1 and L2 of length N, return the maximum number of segments with potholes that can be repaired.

Constraints

• N is an integer within the range [1..200,000].

• Strings L1 and L2 consist only of the characters '.' and 'x'.

Examples

1. Input:

   L1 = "..xx.x."  
   L2 = "x.x.x.."  

   Output: 4 Explanation: It is possible to repair three potholes in the first lane and the first pothole in the second lane without closing the road to traffic.

2. Input:

   L1 = ".xxx...x"  
   L2 = "..x.xxx."  

   Output: 6

3. Input:

   L1 = "xxxxx"  
   L2 = ".x..x"  

   Output: 5

4. Input:

   L1 = "x...x"  
   L2 = "..x.."  

   Output: 2

Answer

public class Solution {
    public int canFix(String L1, String L2) {
        int firstAns = 0, secondAns = 0, thirdAns = 0;
        for (int index = 0; index < L1.length(); index++) {
            if (L1.charAt(index) == 'x') {
                firstAns++;
            }

            if (L2.charAt(index) == 'x') {
                secondAns++;
            }
        }

        // Fill the LTR array with sums
        int[][] leftToRightSum = new int[L1.length()][2];
        int firstRowCounter = 0, secondRowCounter = 0;
        for (int index = 0; index < L1.length(); index++) {
            leftToRightSum[index][0] = firstRowCounter;
            if (L1.charAt(index) == 'x') {
                firstRowCounter++;
            }
            leftToRightSum[index][1] = secondRowCounter;
            if (L2.charAt(index) == 'x') {
                secondRowCounter++;
            }
        }

        // Fill the RTL array with sums
        int[][] rightToLeftSum = new int[L1.length()][2];
        firstRowCounter = 0;
        secondRowCounter = 0;
        for (int index = L1.length() - 1; index >= 0; index--) {
            rightToLeftSum[index][0] = firstRowCounter;
            if (L1.charAt(index) == 'x') {
                firstRowCounter++;
            }
            rightToLeftSum[index][1] = secondRowCounter;
            if (L2.charAt(index) == 'x') {
                secondRowCounter++;
            }
        }

        // Find the point where sum of left side + right side is max
        // This is where the traffic will switch lanes - so we cannot block ith column
        // when calculating
        for (int index = 0; index < L1.length(); index++) {
            if (index == 0) {
                thirdAns = Math.max(thirdAns, Math.max(rightToLeftSum[index][0], rightToLeftSum[index][1]));
            } else if (index == L1.length() - 1) {
                thirdAns = Math.max(thirdAns, Math.max(leftToRightSum[index][0], leftToRightSum[index][1]));
            } else {
                thirdAns = Math.max(thirdAns, Math.max(leftToRightSum[index][0] + rightToLeftSum[index][1],
                        leftToRightSum[index][1] + rightToLeftSum[index][0]));
            }
        }

        return Math.max(firstAns, Math.max(secondAns, thirdAns));
    }

    // A main() for quick tests:
    public static void main(String[] args) {
        Solution sol = new Solution();

        System.out.println(sol.canFix("..xx.x.", "x.x.x.."));
        System.out.println(sol.canFix(".xxx...x", "..x.xxxx"));
        System.out.println(sol.canFix("xxxxx", ".x..x"));
        System.out.println(sol.canFix("x...x", "..x.."));
    }
}