LeetCode

Appearance

1422. Maximum Score After Splitting a String ​

题目 ​

Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).

The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

 

Example 1:

Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

Example 2:

Input: s = "00111"
Output: 5
Explanation: When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5

Example 3:

Input: s = "1111"
Output: 3

 

Constraints:

  • 2 <= s.length <= 500
  • The string s consists of characters '0' and '1' only.
Related Topics
  • 字符串
  • 前缀和

  • 👍 156
  • 👎 0

    • 思路 ​

    字符分割成左右两串，可以采用双向遍历，同时统计左串和右串的 score 前缀和, 双向遍历可以将时间复杂度由迭代法O(N2) 降为 O(N)

    但是创建左右串的前缀和 数组，空间复杂度 O(N)， N = (len(str) - 1) * 2

    解法一 ​

    python
    class Solution:
    def maxScore(self, s: str) -> int:
        ans = 0
        size = len(s)
        subMaxSize = len(s) - 1
        l = [-1] * subMaxSize
        r = [-1] * subMaxSize
        l[0] = 1 if s[0] == '0' else 0
        r[0] = 1 if s[-1] == '1' else 0

        for i, _ in enumerate(l):
            # complementIndex 的范围必须在 [0, 目标数组size - 1]之间
            complementIndex = subMaxSize - i - 1

            if i > 0:
                l[i] =  l[i - 1] if s[i] == '1' else l[i - 1] + 1
                r[i] = r[i - 1] if s[size - 1 - i ] == '0' else r[i - 1]  + 1

            if r[complementIndex] != -1:
                ans = max(ans, l[i] + r[complementIndex])

            if l[complementIndex] != -1:
                ans = max(ans, l[complementIndex] + r[i])

        return ans

    复杂度分析 ​

    • 时间复杂度O(N)
    • 空间复杂度O(N)

    解法二 ​

    python 中的字符串 count 函数可以直接计算出每个字符或者字符串出现的频次。

    可以利用这一属性取代创建前缀和数组, 此时空间复杂度由O(N) -> O(1).

    假设我们可以统计字符‘1’的总长度，从左到右统计字符0的长度，当字符为 ‘0’时，score + 1， 当字符为 ‘1’ 时，score - 1

    py
    # leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def maxScore(self, s: str) -> int:
        left = 1 if s[0] == '0' else 0
        ans = score = left + s[1:].count('1')

        for i in s[1:-1]:
            score = score + 1 if i == '0' else score - 1
            ans = max(ans, score)


        return ans

# leetcode submit region end(Prohibit modification and deletion)

Solution().maxScore("011101")

    复杂度分析 ​

    • 时间复杂度O(N)
    • 空间复杂度O(1)