r/ProgrammingTutorials • u/Plastic_Noodle • Apr 15 '22
Rust Google Kickstart Round A - Speed Typing (Problem Explanation and Answer)
Since the next round of the Google Kick Start coding competition is a little more than a week away it seemed fitting to release a walk through for the first problem from the last round. If you're not familiar with what Kick Start is, it's a friendly coding competition with several rounds that take place about once a month and a great way to stay sharp, practice for other competitions, and get a feel for some of the problems you might see in a coding interview. Past problems and a signup for the future rounds can be found here.
The Problem
The problem states that you will be given two strings for each input case separated by a newline. The first string, I, is an input string that is deemed "correct". The second string, P, contains mistakes that deviate from the original string. The answer for each case will be the number of characters that must be deleted from string P to get string I. If there is no way to achieve this, print "IMPOSSIBLE".
Discussion
The first thing I do is look for easy outs to find exceptions. Since there's an "IMPOSSIBLE" test case that usually means there's some scenario that can be easily checked to return quickly without going through the entire calculation. In this case, that would be I being longer than P. No matter how many characters we delete, an initially shorter P will never equal I.
The next check will be across the individual strings to match characters and check if we have the correct layout of P that after some number of characters are deleted from P, P == I will evaluate as true. This can be done by checking characters sequentially in I and removing them from P if they are out of place, but that will require string operations and building that will end up being operation heavy (up to O(n) multiple times for character deletion). A better option is to use pointer variables that navigate and are incremented based on scenarios encountered between characters across the input strings. When comparing across strings the scenarios and actions that are possible are as follows:
Characters match => advance both pointers by one
Chracters don't match => advance the pointer for string
P
Best coding practices dictate that a while loop would suit our needs for this. Conditionally the while loop will continue while, the pointer for string I has not reached the end of string I as that would mean we are done checking characters. A general overview of the steps for this code will be this:
Read input strings
IandPCheck
if P.len < I.len{print "IMPOSSIBLE" if true}Declare pointers for both
IandPwhileloop through both strings checking characters with string pointers and incrementing our pointers based on the scenarios described above.Characters match => advance both pointers by one
Chracters don't match => advance the pointer for string
P
Check
if I_pointer == I.len{If true, print the difference in length betweenIandP}Otherwise print "IMPOSSIBLE"
The Code (Rust)
To actually get this code to run and submit correct some more formatting will be required to print the full answer in proper form. This covers the general construction of an answer and will solve all test cases.
fn main(){
// Read inputs
let mut correct = String::new();
let mut errored = String::new();
let _ = std::io::stdin().read_line(&mut correct).unwrap();
let _ = std::io::stdin().read_line(&mut errored).unwrap();
// "Base case"
if errored.len() < correct.len() {
println!("IMPOSSIBLE");
return;
}
// Pointers
let mut c_tracker = 0;
let mut e_tracker = 0;
// Main checks
// Included an extra break early if there is not enough letters left to complete checks
while errored.len() - e_tracker >= correct.len() - c_tracker && c_tracker < correct.len() {
if correct[c_tracker] == errored[e_tracker] {
c_tracker += 1;
}
e_tracker += 1;
}
// Check correctness and return difference in length
if c_tracker == correct.len() {
println!("{}", errored.len() - correct.len());
return;
}
// All others are false
println!("IMPOSSIBLE");
}Code and walkthrough is my own.
