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

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