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(&current_candidate) {
		vote_count.insert(current_candidate, 1);
		current_score = 1;
	} else {
		let new_count = vote_count.get(&current_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);
}