Added string compression

tim-harding · Sep 1, 2023 · c23b9e1 · c23b9e1
1 parent 8cbbf55
commit c23b9e1
Show file tree

Hide file tree

Showing 6 changed files with 80 additions and 19 deletions.
diff --git a/README.md b/README.md
@@ -8,7 +8,8 @@ the separate `solutions` module so you won't be influenced by the correct
 answers when approaching problems. Oftentimes, several alternate solutions are
 provided for various constraints. Note that this is supplementary material and
 the book is recommended for additional advice on interviewing, negotiation, and
-how to approach problems. 
+how to approach problems. The book also contains knowledge and design questions
+that don't translate well to this format. 
 
 ## Usage 
 To get started, open the file

diff --git a/src/problems/_01_arrays_and_strings/_06_string_compression.rs b/src/problems/_01_arrays_and_strings/_06_string_compression.rs
@@ -0,0 +1,35 @@
+use std::borrow::Cow;
+
+pub trait StringCompression {
+    /// Implement a method to perform basic string compression using the counts
+    /// of repeated characters. For example, the string aabcccccaaa would become
+    /// a2b1c5a3. If the compressed string would not become smaler than the
+    /// original string, your method should return the original string. You can
+    /// assume the string has only uppercase and lowercase letters.
+    fn string_compression(string: &str) -> Cow<str>;
+}
+
+struct Solution;
+
+impl StringCompression for Solution {
+    fn string_compression(string: &str) -> Cow<str> {
+        // Replace with your solution
+        use crate::solutions::_01_arrays_and_strings::_06_string_compression as solutions;
+        solutions::Solution::string_compression(string)
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn compresses() {
+        assert_eq!(Solution::string_compression("aabcccccaaa"), "a2b1c5a3");
+    }
+
+    #[test]
+    fn returns_original_string() {
+        assert_eq!(Solution::string_compression("abca"), "abca");
+    }
+}
diff --git a/src/problems/_01_arrays_and_strings/mod.rs b/src/problems/_01_arrays_and_strings/mod.rs
@@ -3,3 +3,4 @@ pub mod _02_check_permutation;
 pub mod _03_urlify;
 pub mod _04_palindrome_permutation;
 pub mod _05_one_away;
+pub mod _06_string_compression;
diff --git a/src/solutions/_01_arrays_and_strings/_06_string_compression.rs b/src/solutions/_01_arrays_and_strings/_06_string_compression.rs
@@ -0,0 +1,41 @@
+use crate::problems::_01_arrays_and_strings::_06_string_compression::StringCompression;
+use std::borrow::Cow;
+
+pub struct Solution;
+
+impl StringCompression for Solution {
+    fn string_compression(string: &str) -> Cow<str> {
+        let mut chars = string.chars();
+        let mut previous = match chars.next() {
+            Some(c) => c,
+            None => return Cow::Borrowed(string),
+        };
+        loop {
+            match chars.next() {
+                Some(c) => {
+                    if c == previous {
+                        break;
+                    }
+                    previous = c;
+                }
+                None => return Cow::Borrowed(string),
+            }
+        }
+
+        let mut chars = string.chars();
+        let mut previous = chars.next().unwrap();
+        let mut count = 1u32;
+        let mut out = String::new();
+        for c in chars {
+            if c != previous {
+                out.extend(format!("{previous}{count}").chars());
+                previous = c;
+                count = 1;
+            } else {
+                count += 1;
+            }
+        }
+        out.extend(format!("{previous}{count}").chars());
+        Cow::Owned(out)
+    }
+}
diff --git a/src/solutions/_01_arrays_and_strings/ascii_bitset.rs b/src/solutions/_01_arrays_and_strings/ascii_bitset.rs
diff --git a/src/solutions/_01_arrays_and_strings/mod.rs b/src/solutions/_01_arrays_and_strings/mod.rs
@@ -3,3 +3,4 @@ pub mod _02_check_permutation;
 pub mod _03_urlify;
 pub mod _04_palindrome_permutation;
 pub mod _05_one_away;
+pub mod _06_string_compression;