Welcome to Subscribe On Youtube

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.

 

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)$.

  • 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;
    }
};


  • 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


  • 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;
}

All Problems

All Solutions