1180. Count Substrings with Only One Distinct Letter

leetcode easy

#csharp#easy#leetcode#string#tree#two-pointers

Task

Дана строка s. Верните количество подстрок, которые содержат только одну уникальную букву.

Пример:

Input: s = "aaaba"

Output: 8

Explanation: The substrings with one distinct letter are "aaa", "aa", "a", "b".

"aaa" occurs 1 time.

"aa" occurs 2 times.

"a" occurs 4 times.

"b" occurs 1 time.

So the answer is 1 + 2 + 4 + 1 = 8.

C# solution

matched/original

public class Solution {
    public int CountLetters(string S) {
        int total = 0;
        int left = 0;
        for (int right = 0; right <= S.Length; right++) {
            if (right == S.Length || S[left] != S[right]) {
                int lenSubstring = right - left;
                total += (1 + lenSubstring) * lenSubstring / 2;
                left = right;
            }
        }
        return total;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int CountLetters(string S) {
        int total = 0;
        int left = 0;
        for (int right = 0; right <= S.size(); right++) {
            if (right == S.size() || S[left] != S[right]) {
                int lenSubstring = right - left;
                total += (1 + lenSubstring) * lenSubstring / 2;
                left = right;
            }
        }
        return total;
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int CountLetters(String S) {
        int total = 0;
        int left = 0;
        for (int right = 0; right <= S.length; right++) {
            if (right == S.length || S[left] != S[right]) {
                int lenSubstring = right - left;
                total += (1 + lenSubstring) * lenSubstring / 2;
                left = right;
            }
        }
        return total;
    }
}

Python solution

matched/original

class Solution:
    def countLetters(self, S: str) -> int:
        total = 0
        left = 0

        for right in range(len(S) + 1):
            if right == len(S) or S[left] != S[right]:
                len_substring = right - left
                total += (1 + len_substring) * len_substring // 2
                left = right
        
        return total

Go solution

matched/original

func countLetters(S string) int {
    total := 0
    left := 0

    for right := 0; right <= len(S); right++ {
        if right == len(S) || S[left] != S[right] {
            lenSubstring := right - left
            total += (1 + lenSubstring) * lenSubstring / 2
            left = right
        }
    }

    return total
}

Explanation

Algorithm

Инициализируйте целочисленную переменную total для подсчета количества подстрок, а также два указателя left и right, которые отмечают начало и конец подстроки, содержащей только одну уникальную букву.

Итерируйте по строке S: Если мы не достигли конца и новый символ S[right] такой же, как и начальный символ S[left], увеличьте right на 1 для дальнейшего исследования строки S; в противном случае вычислите длину подстроки как right - left и примените формулу суммы арифметической последовательности; не забудьте установить right в left для начала исследования новой подстроки.

После завершения итерации добавьте к total количество подстрок для последнего сегмента, если он не был учтен. Верните значение total.

😎