carloscn / structstudy

Leetcode daily trainning by using C/C++/RUST programming.
4 stars 1 forks source link

leetcode1876: Substrings of Size Three with Distinct Characters #300

Open carloscn opened 1 year ago

carloscn commented 1 year ago

Description

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.

Example 1:

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".

Example 2:

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".

Constraints:

1 <= s.length <= 100 s​​​​​​ consists of lowercase English letters.

carloscn commented 1 year ago

Analysis

fn count_one_bits(num:usize) -> usize
{
    let mut count:usize = 0;
    let mut input:usize = num;

    while input != 0 {
        input &= input - 1;
        count += 1;
    }

    return count;
}

pub fn count_good_substrings(s: &str) -> i32
{
    if s.len() < 1 {
        return 0;
    }

    let mut ret:i32 = 0;
    let mut s_v:Vec<char> = s.chars().collect();
    let (mut i, mut j, mut k, mut num, mut n) =
        (0usize, 3usize, 0usize, (1 << s.len()) as usize, 0usize);

    for n in 0..num {
        if count_one_bits(n) != 3 {
            continue;
        }

        j = n;
        k = 0;
        i = 0;
        let mut t_buf:Vec<char> = vec!['0'; 3];
        while j != 0 {
            if j & 1 == 1 {
                t_buf[i] = s_v[k];
                i += 1;
            }
            j >>= 1;
            k += 1;
        }
        t_buf.sort();
        t_buf.dedup();
        if t_buf.len() == 3 {
            println!("the result is {:?}\n", t_buf);
            ret += 1;
        }

    }
    return ret;
}
carloscn commented 1 year ago

Code

https://review.gerrithub.io/c/carloscn/structstudy/+/557487 https://github.com/carloscn/structstudy/commit/c9e20c28573ebe571b4c74796d8025cbdd15a280