# Problem C - Count XXX

## Principle

Given a string S, the objective is to count the number of distinct sub-strings of S which are a repetition of the same character.
For example, `aabcaa`

contains 4 substrings: `a`

, `aa`

, `b`

, `c`

. Note that `a`

and `aa`

appear twice in S but are counted only once.

## My solution

I wasted some time because I didn’t read the problem properly. 🤦♂️
I wanted to figure out the sub-strings only in O(n) complexity, i.e. in one pass.
To do this, we just need to remember one current character and count the repetitions.
When the character changes, we change the actual substring.
In a first version, I kept the current character and the current substring as loop variables.
To determine if a substring was already present before, I use a `HashMap`

so that the lookup is of constant time.
The question becomes *what do I use as the hashmap key?*
First I used the actual substring.
The issue is that storing all those substrings takes *A LOT* of memory, especially since I store all the lengths.
The original string max length is 2E5, which is a lot of memory if we want to store all the substrings for keys.
*The hint*: Actually all the keys contain only one character, repeated. So we just need to store the character and the substring length as a key.

## The Code

```
let mut cur_char: char = s[0];
let mut cur_len: usize = 1;
let mut substr_hash: HashMap<(char, usize), usize> = HashMap::new();
substr_hash.insert( (s[0],1) , 1);
for i in 1..n {
if cur_char != s[i] {
// We change character
substr_hash.insert((cur_char, cur_len ), 1);
cur_len = 1;
cur_char = s[i];
} else {
substr_hash.insert((cur_char, cur_len), 1);
cur_len = cur_len +1;
}
}
// We need to process the last substring
substr_hash.insert((cur_char, cur_len), 1);
println!("{}", substr_hash.len());
```

# Problem D - Election Quick Report

## The principle

We organize an election between N candidates. We read vote by vote, and for each vote we need to print the ID of the candidate who has the most votes

## My solution

The problem is actually pretty simple.
We keep the scores of all candidates in a `HashMap`

for quick access.
The brute force solution would be to compare all the votes then in order to find the leading candidate. However it is too slow.
*The hint*: The only candidate whose score changes is the one who just received a vote. Either this candidate becomes the leader, or the leader stays unchanged.
Therefore we just need to keep as a loop variable the score and the index of the leading candidate.
Unfortunately I submitted this solution less than one minute too late so I didn’t get any points for it…

```
let mut vote_count: HashMap<usize, usize> = HashMap::new();
let mut max_score: usize = 0;
let mut max_candidate: usize = 0;
for i in 0..m {
// Recording the current vote
let current_candidate = a[i];
let current_score;
if !vote_count.contains_key(¤t_candidate) {
vote_count.insert(current_candidate, 1);
current_score = 1;
} else {
let new_count = vote_count.get(¤t_candidate).unwrap() + 1;
vote_count.insert(current_candidate, new_count);
current_score = new_count;
}
// Now let's figure out the winner for this round
if current_score > max_score {
max_score = current_score;
max_candidate = current_candidate;
} else {
// Rule which says that in case of equal scores,
// the candidate with the smallest index leads
if current_score == max_score {
max_candidate = current_candidate.min(max_candidate);
}
}
println!("{}", max_candidate);
}
```