3707. Equal Score Substrings

Description

You are given a string s consisting of lowercase English letters.

The score of a string is the sum of the positions of its characters in the alphabet, where 'a' = 1, 'b' = 2, ..., 'z' = 26.

Determine whether there exists an index i such that the string can be split into two non-empty substrings s[0..i] and s[(i + 1)..(n - 1)] that have equal scores.

Return true if such a split exists, otherwise return false.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

Input: s = "adcb"

Output: true

Explanation:

Split at index i = 1:

Left substring = s[0..1] = "ad" with score = 1 + 4 = 5
Right substring = s[2..3] = "cb" with score = 3 + 2 = 5

Both substrings have equal scores, so the output is true.

Example 2:

Input: s = "bace"

Output: false

Explanation:

No split produces equal scores, so the output is false.

Constraints:

2 <= s.length <= 100
s consists of lowercase English letters.

Solutions

Solution 1: Prefix Sum

We first calculate the total score of the string, denoted as \(r\). Then we traverse the first \(n-1\) characters from left to right, calculating the prefix score \(l\) and updating the suffix score \(r\). If at some position \(i\), the prefix score \(l\) equals the suffix score \(r\), it means there exists an index \(i\) that can split the string into two substrings with equal scores, so we return \(\textit{true}\). If we finish traversing without finding such an index, we return \(\textit{false}\).

The time complexity is \(O(n)\), where \(n\) is the length of the string. The space complexity is \(O(1)\).

Python3JavaC++GoTypeScript

class Solution:
    def scoreBalance(self, s: str) -> bool:
        l = 0
        r = sum(ord(c) - ord("a") + 1 for c in s)
        for c in s[:-1]:
            x = ord(c) - ord("a") + 1
            l += x
            r -= x
            if l == r:
                return True
        return False

class Solution {
    public boolean scoreBalance(String s) {
        int n = s.length();
        int l = 0, r = 0;
        for (int i = 0; i < n; ++i) {
            int x = s.charAt(i) - 'a' + 1;
            r += x;
        }
        for (int i = 0; i < n - 1; ++i) {
            int x = s.charAt(i) - 'a' + 1;
            l += x;
            r -= x;
            if (l == r) {
                return true;
            }
        }
        return false;
    }
}

class Solution {
public:
    bool scoreBalance(string s) {
        int l = 0, r = 0;
        for (char c : s) {
            int x = c - 'a' + 1;
            r += x;
        }
        for (int i = 0; i < s.size() - 1; ++i) {
            int x = s[i] - 'a' + 1;
            l += x;
            r -= x;
            if (l == r) {
                return true;
            }
        }
        return false;
    }
};

func scoreBalance(s string) bool {
    var l, r int
    for _, c := range s {
        x := int(c-'a') + 1
        r += x
    }
    for _, c := range s[:len(s)-1] {
        x := int(c-'a') + 1
        l += x
        r -= x
        if l == r {
            return true
        }
    }
    return false
}

function scoreBalance(s: string): boolean {
    let [l, r] = [0, 0];
    for (const c of s) {
        const x = c.charCodeAt(0) - 96;
        r += x;
    }
    for (let i = 0; i < s.length - 1; ++i) {
        const x = s[i].charCodeAt(0) - 96;
        l += x;
        r -= x;
        if (l === r) {
            return true;
        }
    }
    return false;
}

3707. Equal Score Substrings

Description

Solutions

Solution 1: Prefix Sum

Comments