Skip to content

3760. Maximum Substrings With Distinct Start

Description

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

Return an integer denoting the maximum number of substrings you can split s into such that each substring starts with a distinct character (i.e., no two substrings start with the same character).

 

Example 1:

Input: s = "abab"

Output: 2

Explanation:

  • Split "abab" into "a" and "bab".
  • Each substring starts with a distinct character i.e 'a' and 'b'. Thus, the answer is 2.

Example 2:

Input: s = "abcd"

Output: 4

Explanation:

  • Split "abcd" into "a", "b", "c", and "d".
  • Each substring starts with a distinct character. Thus, the answer is 4.

Example 3:

Input: s = "aaaa"

Output: 1

Explanation:

  • All characters in "aaaa" are 'a'.
  • Only one substring can start with 'a'. Thus, the answer is 1.

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English letters.

Solutions

Solution 1

Thinking

Each piece must start with a distinct character, so there are at most \(|\Sigma|\) pieces and each character that appears can start at most one of them. Every distinct character can form its own piece, hence the answer is the number of distinct letters in \(s\).

1
2
3
class Solution:
    def maxDistinct(self, s: str) -> int:
        return len(set(s))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int maxDistinct(String s) {
        int ans = 0;
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            if (++cnt[s.charAt(i) - 'a'] == 1) {
                ++ans;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int maxDistinct(string s) {
        int ans = 0;
        int cnt[26]{};
        for (char c : s) {
            if (++cnt[c - 'a'] == 1) {
                ++ans;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func maxDistinct(s string) (ans int) {
    cnt := [26]int{}
    for _, c := range s {
        cnt[c-'a']++
        if cnt[c-'a'] == 1 {
            ans++
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function maxDistinct(s: string): number {
    let ans = 0;
    const cnt: number[] = Array(26).fill(0);
    for (const ch of s) {
        const idx = ch.charCodeAt(0) - 97;
        if (++cnt[idx] === 1) {
            ++ans;
        }
    }
    return ans;
}

Comments