1238. Algorithm - String
String and Array


Common approaches for solving string and array problems

1. String

  • Presum
  • Two Pointers
  • Split to Left and Right

Examples for Split to Left and Right:

2. Questions

2.1 Min Deletions To Obtain String in Right Format

We are given a string S of length N consisting only of letters A and/or B. Our goal is to obtain a string in the format A...AB...B(all letters A occur before all letters B) by deleting some letters from S. In particular, strings consisting only of letters A or only of letters B fit this format.

Write a function that, given a string S, return the minimum number of letters that need to be deleted from S in order to obtain a string in the above format.

  • N is an integer within the range [1,100000];
  • string S consists only of the characters A and/or B.

Example Example 1

Input: "BAAABAB"
Output: 2
Explanation: We can obtain "AAABB" by deleting the first occurrence of 'B' and the last occurrence of 'A'.

Example 2

Input: "BBABAA"
Output: 3
Explanation: We can delete all occurrences of 'A' or 'B'.

Example 3

Input: "AABBBB"
Output: 0
Explanation: We do not have to delete any letters, because the given string is already in the expected format.

Solution: First, go through the string, count the number of B at left side and the number of A at right side. Then, find the minimum sum of left B and right A at each position. The key concept of the solution is to divide the array/string into left and right parts.

// time: O(n), space: O(n)
public int minDeletionsToObtainStringInRightFormat3(String s) {
    // Go through the string, count the number of B at left side and the number of A at right side.
    // Then, find the minimum sum of left B and right A at each position.
    if (s == null || s.length() == 0) {
        return 0;
    }

    int n = s.length();
    int[] left = new int[n];  // number of B from left
    int[] right = new int[n]; // number of A from right
    left[0] = s.charAt(0) == 'B' ? 1 : 0;
    for (int i = 1; i < n; i++) {
        left[i] = left[i - 1];
        if (s.charAt(i) == 'B') {
            left[i]++;
        }

    }

    right[n - 1] = s.charAt(n - 1) == 'A' ? 1 : 0;
    for (int i = n - 2; i >= 0; i--) {
        right[i] = right[i + 1];
        if (s.charAt(i) == 'A') {
            right[i]++;
        }
    }

    int min = n;
    for (int i = 0; i < n; i++) {
        int count = 0;
        if (i == 0) {
            count = right[i + 1];
        } else if (i == n - 1) {
            count = left[i - 1];
        } else {
            count = left[i - 1] + right[i + 1];
        }
        min = Math.min(min, count);
    }

    return min;
}

Optimized space solution.

// time: O(n), space: O(1)
public int minDeletionsToObtainStringInRightFormat2(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    int n = s.length();

    int leftB = 0;
    int rightA = 0;

    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == 'A') {
            rightA++;
        }
    }

    int ans = rightA;

    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == 'A') {
            rightA--;
        } else {
            leftB++;
        }
        ans = Math.min(ans, rightA + leftB);
    }

    return ans;
}

Further, one pass solution.

// one pass: time: O(n), space: O(1)
public int minDeletionsToObtainStringInRightFormat(String s) {
    if (s == null || s.isEmpty()) {
        return 0;
    }

    int countA = 0;
    int countB = 0;
    int toDelete = 0;

    for (char c : s.toCharArray()) {
        if (c == 'A') {
            countA++;
            if (countB > toDelete) {
                toDelete++;
            }
        } else {
            countB++;
        }
    }

    return Math.min(countA, Math.min(countB, toDelete));
}

5. Source Files

7. References