LeetCode 1876. Substrings of Size Three with Distinct Characters
はじめに
LeetCode 「1876. Substrings of Size Three with Distinct Characters」の問題をGoで解きました。
問題
問題文
A string is good if there are no repeated characters.
Given a string s, return the number of good substrings of length three in s.
Note that if there are multiple occurrences of the same substring, every occurrence should be counted.
A substring is a contiguous sequence of characters in a string.
和訳
文字列は、重複した文字がない場合に適切です。
文字列 s が与えられた場合、s の内の長さ 3 の適切な部分文字列の数を返します。
同じ部分文字列が複数回出現する場合は、すべての出現をカウントする必要があることに注意してください。
部分文字列とは、文字列中の連続した文字列のことです。
例
Input: s = "xyzzaz"
Output: 1
Explanation: There are 4 substrings of size 3: "xyz", "yzz", "zza", and "zaz".
The only good substring of length 3 is "xyz".
Input: s = "aababcabc"
Output: 4
Explanation: There are 7 substrings of size 3: "aab", "aba", "bab", "abc", "bca", "cab", and "abc".
The good substrings are "abc", "bca", "cab", and "abc".
制約
- 1 <= s.length <= 100
- s consists of lowercase English letters.
解答1
与えられた文字列の中から3文字の文字列を作っていき、その中に文字の重複がないものをカウントする問題です。
まず、シンプルな方法を考えました。
例1だと、以下のように3文字が作られます。
- "xyz"
x y z z a z
↑ ↑ ↑
- "yzz"
x y z z a z
↑ ↑ ↑
- "zza"
x y z z a z
↑ ↑ ↑
- "zaz"
x y z z a z
↑ ↑ ↑
3文字の先頭を示すインデックスを1つずつ移動しながら部分文字列を検証して、文字の重複がなければカウントするという流れで実装できそうです。
コード
func countGoodSubstrings(s string) int {
count := 0
if len(s) < 3 {
return count
}
for i := 0; i < len(s)-2; i++ {
if s[i] != s[i+1] && s[i] != s[i+2] && s[i+1] != s[i+2] {
count++
}
}
return count
}
制約上、文字列の長さが1や2の場合があるので、3文字未満であればreturnしています。
インデックスがlen(s)-2以降は3文字を作ることができないので、条件にはi < len(s)-2を指定しています。
if文では、3文字に重複がないかを検証して、重複がなければカウントを増やしています。
計算量
- 時間的計算量：O(n)
- 空間的計算量：O(1)
解答2（セットを使用）
他のアプローチも紹介します。
3文字に重複した文字がないかを確認する処理で、セットを使う方法です。
コード
func countGoodSubstrings(s string) int {
count := 0
if len(s) < 3 {
return count
}
for i := 0; i < len(s)-2; i++ {
m := make(map[byte]bool)
m[s[i]] = true
m[s[i+1]] = true
m[s[i+2]] = true
if len(m) == 3 {
count++
}
}
return count
}
各ループでbyteをキーとしたmapを作成しています。
ここで、すべての文字が異なる場合は、それぞれの文字のキーに値が入ります。
重複がある場合は、重複された文字にはtrueが再代入されます。
len関数でmap内のアイテムの数を取得することですべての文字が異なるかを判定できます。
このパターンだと、今回より部分文字列が長い時にも応用しやすいですね。
計算量
- 時間的計算量：O(n)
- 空間的計算量：O(1)
Discussion