Problem I solved

1. Two Sum

Note that if you run these two implementation in release mode, the second implementation fails because it does not take into consideration the overflow.

use std::collections::HashMap;

fn main() {
    let data: [i8; 4] = [-128, -1, 12, 13];
    let target = 127;
    if let Some(indice) = two_sum(&data, target) {
        println!("Correct Two Sum found: {indice:?}");
    } else {
        println!("Correct Two Sum did not find a result ")
    }

    if let Some(indice) = two_sum_2(&data, target) {
        println!("Incorrect Two Sum found: {indice:?}");
    } else {
        println!("Incorrect Two Sum did not find a result ")
    }
}

fn two_sum(data: &[i8], target: i8) -> Option<(usize, usize)> {
    let mut my_map: HashMap<i8, usize> = HashMap::new();

    for (idx, item) in data.iter().enumerate() {
        if let Some(val) = target.checked_sub(*item) {
            if let Some(&jdx) = my_map.get(&val) {
                return Some((jdx, idx));
            }
        }
        my_map.insert(*item, idx);
    }
    None
}

fn two_sum_2(data: &[i8], target: i8) -> Option<(usize, usize)> {
    let mut my_map: HashMap<i8, usize> = HashMap::new();

    for (idx, item) in data.iter().enumerate() {
        let val = target - *item;
        println!("{val}");
        if let Some(&jdx) = my_map.get(&val) {
            return Some((jdx, idx));
        }
        my_map.insert(*item, idx);
    }
    None
}

2. Is Palindrome

#![allow(unused)]
fn main() {
impl Solution {
    pub fn is_palindrome(x: i32) -> bool {
        // 1. Handle edge cases:
        //    a. Negative numbers cannot be palindromes (e.g., -121 reads as 121-).
        //    b. Numbers ending in 0 (e.g., 10, 120) cannot be palindromes unless the number itself is 0.
        //       (If x % 10 == 0 and x != 0, its reversed form would not match, as it wouldn't start with 0).
        if x < 0 || (x % 10 == 0 && x != 0) {
            return false;
        }

        let mut num = x;
        let mut reverted_number = 0;

        // 2. Reverse half of the number:
        // We build `reverted_number` by taking digits from the end of `num`
        // and appending them to `reverted_number`.
        // We stop when `num` becomes less than or equal to `reverted_number`.
        // This means we've processed roughly half of the digits.
        while num > reverted_number {
            reverted_number = reverted_number * 10 + num % 10; // Add the last digit of num to reverted_number
            num /= 10; // Remove the last digit from num
        }

        // 3. Compare the original number (or its first half) with the reversed half:
        //
        // Case A: The original number had an even number of digits.
        // Example: x = 1221
        //   - Iter 1: num = 122, reverted_number = 1
        //   - Iter 2: num = 12, reverted_number = 12
        //   - Loop terminates because num (12) is not > reverted_number (12).
        //   In this case, `num` and `reverted_number` should be exactly equal.
        //
        // Case B: The original number had an odd number of digits.
        // Example: x = 121
        //   - Iter 1: num = 12, reverted_number = 1
        //   - Iter 2: num = 1, reverted_number = 12
        //   - Loop terminates because num (1) is not > reverted_number (12).
        //   In this case, `reverted_number` will have one extra digit (the middle digit)
        //   compared to `num`. We need to remove this middle digit from `reverted_number`
        //   for a correct comparison (e.g., 12 / 10 = 1, which matches `num`).

        num == reverted_number || num == reverted_number / 10
    }
}
}

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Note: Since it is guaranteed that all characters are English letters, we could use as_bytes()

#![allow(unused)]
fn main() {
impl Solution {
    pub fn valid_palindrome(s: String) -> bool {
        // Use as_bytes() for efficient O(1) indexing.
        // This is safe because the problem guarantees lowercase English letters.
        let bytes = s.as_bytes();
        let mut left = 0;
        let mut right = s.len() - 1;

        while left < right {
            if bytes[left] != bytes[right] {
                // Mismatch found! We must use our one deletion.
                // Check both possibilities:
                // 1. Delete the left character
                // 2. Delete the right character
                return Self::is_palindrome_slice(bytes, left + 1, right) ||
                       Self::is_palindrome_slice(bytes, left, right - 1);
            }
            // No mismatch, shrink the window
            left += 1;
            right -= 1;
        }

        // The loop finished without mismatches,
        // so it was already a palindrome (0 deletions).
        true
    }

    /// Helper function to check if a sub-slice is a palindrome.
    fn is_palindrome_slice(bytes: &[u8], mut left: usize, mut right: usize) -> bool {
        while left < right {
            if bytes[left] != bytes[right] {
                return false;
            }
            left += 1;
            right -= 1;
        }
        true
    }
}
}

#![allow(unused)]
fn main() {
fn merge_alternately_std(word1: String, word2: String) -> String {
    // 1. Efficiency: Pre-allocate the string to its final size.
    // We use .len() (bytes) which is a fast O(1) lower bound.
    // **Note:** both len() and with_capacity are using byte for the size
    let mut result = String::with_capacity(word1.len() + word2.len());

    // 2. Idiomatic: Get char iterators.
    let mut chars1 = word1.chars();
    let mut chars2 = word2.chars();

    // 3. Idiomatic: Loop based on the iterators themselves.
    loop {
        // Use `match` to handle all cases cleanly without unwrap()
        match (chars1.next(), chars2.next()) {
            // Both strings still have chars
            (Some(c1), Some(c2)) => {
                result.push(c1);
                result.push(c2);
            }
            // Only word1 has chars
            (Some(c1), None) => {
                result.push(c1);
                // 4. Idiomatic: Once word2 is done, just extend with the rest
                //    of word1 and break.
                result.extend(chars1);
                break;
            }
            // Only word2 has chars
            (None, Some(c2)) => {
                result.push(c2);
                result.extend(chars2);
                break;
            }
            // Both are empty
            (None, None) => {
                break;
            }
        }
    }

    result
}
}

fn check_same_digits(mut num1: u32, mut num2: u32) -> bool {
    let mut counts = [0; 10];

    while num1 > 0 {
        counts[(num1 % 10) as usize] += 1;
        num1 /= 10;
    }

    while num2 > 0 {
        counts[(num2 % 10) as usize] -= 1;
        num2 /= 10;
    }

    counts.iter().all(|&c| c == 0)
}

fn main() {
    let c = check_same_digits(12, 21);
    if c {
        println!("YES");
    } else {
        println!("NO");
    }
}

LRU Cache in Rust

Problem Statement

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity): Initialize the LRU cache with a positive size capacity.
• int get(int key): Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value): Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Approach

Designing an LRU Cache is a classic problem that tests your understanding of data structures and their performance characteristics.
To achieve O(1) time complexity for both get and put operations, a single data structure like a Vec or a HashMap is insufficient.

The optimal solution involves two data structures:

1. HashMap for O(1) average time lookups — mapping a key to a node in a linked list.
2. Doubly-Linked List to maintain the order of usage — allowing O(1) insertion and deletion from anywhere when we have the node.

Strategy

• The doubly-linked list stores (key, value) pairs in order of recency.
• The head is the most recently used item, the tail is the least recently used.
• The HashMap maps a key to its corresponding Node in the list.

Operations

put(key, value):

• If the key exists: update the node's value and move it to the head.
• If the key doesn't exist: create a node.
• If capacity is reached: evict the tail node (LRU) and remove it from the HashMap.
• Insert the new node at the head.

get(key):

• If the key exists: move the node to the head and return its value.
• If not: return -1.

Rust Implementation

We use Rc<RefCell<T>> and Weak<T> to manage shared ownership and prevent reference cycles in the doubly-linked list.

#![allow(unused)]
fn main() {
use std::collections::HashMap;
use std::cell::RefCell;
use std::rc::{Rc, Weak};

// A pointer to a node. Using Rc for shared ownership.
type Link = Option<Rc<RefCell<Node>>>;
// A weak pointer to a node, to prevent reference cycles.
type WeakLink = Option<Weak<RefCell<Node>>>;

// Node in the doubly-linked list
struct Node {
    key: i32,
    value: i32,
    prev: WeakLink,
    next: Link,
}

impl Node {
    fn new(key: i32, value: i32) -> Self {
        Node { key, value, prev: None, next: None }
    }
}

pub struct LRUCache {
    capacity: usize,
    map: HashMap<i32, Rc<RefCell<Node>>>,
    head: Link,
    tail: Link,
}


/** * Note: The provided LeetCode template uses `&self` for `get` and `put`.
 * This is incorrect because these methods need to modify the cache's internal
 * state (the order of the list and the map). We must use `&mut self`.
 */
impl LRUCache {

    pub fn new(capacity: i32) -> Self {
        LRUCache {
            capacity: capacity as usize,
            map: HashMap::with_capacity(capacity as usize),
            head: None,
            tail: None,
        }
    }
    
    pub fn get(&mut self, key: i32) -> i32 {
        if let Some(node_rc) = self.map.get(&key).cloned() {
            // The node exists. Move it to the front of the list.
            self.detach_and_move_to_front(&node_rc);
            // Return its value.
            let value = node_rc.borrow().value;
            value
        } else {
            // The key doesn't exist.
            -1
        }
    }
    
    pub fn put(&mut self, key: i32, value: i32) {
        if let Some(node_rc) = self.map.get(&key).cloned() {
            // Key already exists. Update value and move to front.
            node_rc.borrow_mut().value = value;
            self.detach_and_move_to_front(&node_rc);
        } else {
            // Key is new. Check capacity.
            if self.map.len() == self.capacity {
                // Evict the least recently used item (the tail).
                if let Some(tail_rc) = self.tail.take() {
                    let key_to_evict = tail_rc.borrow().key;
                    self.map.remove(&key_to_evict);
                    // Update the tail to be the previous node.
                    if let Some(prev_weak) = tail_rc.borrow_mut().prev.take() {
                        if let Some(prev_rc) = prev_weak.upgrade() {
                            prev_rc.borrow_mut().next = None;
                            self.tail = Some(prev_rc);
                        }
                    } else {
                        // The list is now empty.
                        self.head = None;
                    }
                }
            }
            
            // Create the new node and add it to the front.
            let new_node_rc = Rc::new(RefCell::new(Node::new(key, value)));
            self.push_front(&new_node_rc);
            self.map.insert(key, new_node_rc);
        }
    }

    // --- Helper Methods for List Manipulation ---

    /// Moves an existing node to the front of the list.
    fn detach_and_move_to_front(&mut self, node_rc: &Rc<RefCell<Node>>) {
        // If the node is already the head, do nothing.
        if self.head.as_ref().map_or(false, |h| Rc::ptr_eq(h, node_rc)) {
            return;
        }

        self.detach(node_rc);
        self.push_front(node_rc);
    }

    /// Detaches a node from the list by linking its neighbors.
    fn detach(&mut self, node_rc: &Rc<RefCell<Node>>) {
        let mut node = node_rc.borrow_mut();
        let prev_weak = node.prev.take();
        let next_rc = node.next.take();

        if let Some(prev_node) = prev_weak.as_ref().and_then(|w| w.upgrade()) {
            prev_node.borrow_mut().next = next_rc.clone();
        } else {
            // This was the head node.
            self.head = next_rc.clone();
        }

        if let Some(next_node) = next_rc.as_ref() {
            next_node.borrow_mut().prev = prev_weak;
        } else {
            // This was the tail node.
            self.tail = prev_weak.and_then(|w| w.upgrade());
        }
    }

    /// Pushes a new node to the front (head) of the list.
    fn push_front(&mut self, node_rc: &Rc<RefCell<Node>>) {
        node_rc.borrow_mut().next = self.head.clone();
        node_rc.borrow_mut().prev = None;

        if let Some(old_head) = self.head.as_ref() {
            old_head.borrow_mut().prev = Some(Rc::downgrade(node_rc));
        }
        
        self.head = Some(node_rc.clone());

        if self.tail.is_none() {
            // If the list was empty, this node is both head and tail.
            self.tail = Some(node_rc.clone());
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * let mut obj = LRUCache::new(capacity);
 * let ret_1: i32 = obj.get(key);
 * obj.put(key, value);
 */
}

fn main() {
    let mut result = pascan_triangle(5);

    for (rdx, row) in result.iter().enumerate() {
        for (cdx, col) in row.iter().enumerate() {
            println!("{},{} = {}", rdx, cdx, col)
        }
        println!();
    }
}
fn pascan_triangle(num_rows: i32) -> Vec<Vec<i32>> {
    // If the number of rows is 0, return an empty vector.
    if num_rows == 0 {
        return vec![];
    }

    // Initialize the triangle with the first row.
    let mut triangle = vec![vec![1]];

    // Iterate from the second row up to the desired number of rows.
    for i in 1..num_rows as usize {
        // Get a reference to the previous row.
        let prev_row = &triangle[i - 1];
        // Start the new row with 1.
        let mut new_row = vec![1];

        // Calculate the middle elements of the new row.
        // Each element is the sum of the two elements directly above it.
        for j in 1..prev_row.len() {
            new_row.push(prev_row[j - 1] + prev_row[j]);
        }

        // End the new row with 1.
        new_row.push(1);
        // Add the newly created row to the triangle.
        triangle.push(new_row);
    }

    // Return the complete triangle.
    triangle
}

fn main() {
    let data = vec![String::from("Ahmad"), String::from("Ahmar")];
    let result = longest_common_prefix(data);
    println!("{}", result);
    println!("Hello");
}

fn longest_common_prefix(strs: Vec<String>) -> String {
    let result = String::new();

    if strs.is_empty() {
        return result;
    }

    let first_string = &strs[0];
    let mut char_index = 0;
    for (idx, ch) in first_string.bytes().enumerate() {
        for j in 1..strs.len() {
            let current_string = &strs[j];

            if idx > current_string.len() || current_string.as_bytes()[idx] != ch {
                return first_string[..idx].to_string();
            }
        }
        char_index += 1;
    }
    first_string[0..char_index].to_string()
}

fn main() {
    let samples = vec!["()", "()[]{}", "(]", "([])", "([)]"];
    for sample in samples {
        println!("{} is {}", sample, valid_parentheses(sample));
    }
}


fn  valid_parentheses(s: &str) -> bool {
    let mut stk = Vec::new();
    for ch in s.chars() {
        match ch {
            '{' | '(' | '[' => {
                stk.push(ch);
            }
            ')' => {
                if stk.pop() != Some('(') {
                    return false;
                }
            }
            '}' => {
                if stk.pop() != Some('{') {
                    return false;
                }
            }
            ']' => {
                if stk.pop() != Some('[') {
                    return false;
                }
            }
            _ => (),
        }
    }
    stk.is_empty()
}

fn main() {
    let mut samples = vec![7,1,5,3,6,4];
    println!("{}", best_time_to_buy_and_sell_stock(samples));
}

fn best_time_to_buy_and_sell_stock(prices: Vec<i32>) -> i32 {
    let mut result = 0;
    let mut min = i32::MAX;
    for price in prices {
        result = result.max(price-min);
        min = min.min(price);
    }
    result
}

#![allow(unused)]

fn main() {
fn num_of_unplaced_fruits(fruits: &Vec<i32>, baskets: &Vec<i32>) -> i32 {
    let mut used = vec![false; baskets.len()];
    for &fruit in fruits {
        for (idx, &basket) in baskets.iter().enumerate() {
            if !used[idx] && basket >= fruit {
                used[idx] = true;
                break;
            }
        }
    }
    used.iter().filter(|item| **item != true).count() as i32
}

fn single_number(nums: Vec<i32>) -> i32 {
    let mut result = 0;
    for item in nums {
        result ^= item
    }
    result
}

fn is_anagram(s: String, t: String) -> bool {
    let mut hash_map: HashMap<char, i32> = HashMap::new();

    for ch in s.chars() {
        hash_map
            .entry(ch)
            .and_modify(|count| *count += 1)
            .or_insert(1);
    }

    for ch in t.chars() {
        hash_map
            .entry(ch)
            .and_modify(|count| *count -= 1)
            .or_insert(-1);
    }

    hash_map.iter().filter(|(_, item)| **item != 0).count() == 0
}

fn majority_element(nums: Vec<i32>) -> i32 {
    let mut candidate = 0;
    let mut count = 0;

    for num in nums {
        if count == 0 {
            candidate = num;
        }

        if num == candidate {
            count += 1;
        } else {
            count -= 1;
        }
    }
    candidate
}

fn power_of_three(num: i32) -> bool {
    let mut num = num;
    if num <= 0 {
        return false;
    }
    while (num % 3 == 0) {
        num /= 3;
    }
    num == 1
}



fn roman_to_int(s: String) -> i32 {
    let mut result = 0;
    let mut prev_value = 0;

    for ch in s.chars().rev() {
        let current_value = match ch {
            'I' => 1,
            'V' => 5,
            'X' => 10,
            'L' => 50,
            'C' => 100,
            'D' => 500,
            'M' => 1000,
            _ => 0,
        };
        if current_value < prev_value {
            println!(
                current_value, prev_value
            );
            result -= current_value;
        } else {
            println!(
                current_value, prev_value
            );
            result += current_value;
        }
        prev_value = current_value;
    }

    result
}


pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
    if nums.is_empty() {
        return 0;
    }

    let mut low: i32 = 0;
    let mut high: i32 = (nums.len() - 1) as i32;

    // Use a while loop with low <= high
    while low <= high {
        // Use an unsigned type for mid to avoid cast warnings.
        let mid = low + (high - low) / 2;
        let mid_val = nums[mid as usize];

        if mid_val == target {
            return mid;
        } else if mid_val < target {
            // Target is in the right half
            low = mid + 1;
        } else {
            // Target is in the left half
            high = mid - 1;
        }
    }

    // After the loop, `low` is the correct insertion point.
    low
}

fn largest_good_integer(num: String) -> String {
    let mut best = String::new();
    let chars: Vec<char> = num.chars().collect();

    for i in 0..=chars.len().saturating_sub(3) {
        if chars[i] == chars[i + 1] && chars[i] == chars[i + 2] {
            let candidate = chars[i].to_string().repeat(3);
            if candidate > best {
                best = candidate;
            }
        }
    }

    best
}

fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
    if nums.is_empty() {
        return 0;
    }
    let mut i =0;

    for j in 0..nums.len() {
        if nums[j] != nums[i] {
            i += 1;
            nums[i] = nums[j];
        }
    }
    (i+1) as i32
}


pub fn str_str(haystack: String, needle: String) -> i32 {
        let haystack: Vec<char> = haystack.chars().collect();
        let needle: Vec<char> = needle.chars().collect();
    
        let ns = needle.len();
        let hs = haystack.len();

        if hs < ns {
            return -1;
        }
        println!("ns = {}", ns);
        println!("hs = {}", hs);
    
        'first_loop: for i in 0..=(hs - ns) {
            for j in 0..ns {
                if needle[j] != haystack[i + j] {
                    continue 'first_loop;
                }
            }
            return i as i32;
        }
        -1 
    }
}

fn move_zeroes(nums: &mut Vec<i32>) {
    let mut j = 0;
    for i in 0..nums.len() {
        if nums[i] != 0 {
            nums[j] = nums[i];
            j += 1;
        }
    }
    for i in j..nums.len() {
        nums[i as usize] = 0;
    }
}

fn maximum69_number(num: i32) -> i32 {
    let mut num = num;
    let result = num;

    let mut level: i32 = -1;
    let mut r_level = -1;

    while num > 0 {
        level += 1;
        if num % 10 == 6 {
            r_level = level;
        }
        num /= 10;
    }
    if r_level >= 0 {
        let added_value = 3 * 10i32.pow(r_level as u32);
        return result + added_value;
    }
    result
}
}

Question:

Is the implementation below fine? I am also familiar with .count_ones()

#![allow(unused)]
fn main() {
// Corrected version of your function
// Using u32 is more idiomatic for bitwise operations to avoid sign bit issues
fn hamming_weight_iterative(n: u32) -> i32 {
    let mut result = 0;
    for i in 0..32 {
        if (1 << i) & n != 0 {
            result += 1
        }
    }
    result
}
}

Better Solutions for Calculating Hamming Weight

The main drawback of this method is that it always performs 32 iterations, regardless of the input. If n is 1, it still needlessly checks the 31 other bits.

Here are some better solutions, ordered from a simple improvement to the most optimal approach.

1. Brian Kernighan's Algorithm

This is a classic and very elegant improvement. The trick is to realize that the operation n & (n - 1) clears the least significant set bit (the rightmost '1').

By repeatedly applying this operation until the number becomes 0, you can count exactly how many set bits there were.

How it works:

• Let n = 12 (binary 1100).
• n - 1 = 11 (binary 1011).
• n & (n - 1) is 1100 & 1011 = 1000 (which is 8). The rightmost '1' has been cleared.
• The loop runs as many times as there are set bits.

The Code:

#![allow(unused)]
fn main() {
fn hamming_weight_kernighan(mut n: u32) -> i32 {
    let mut count = 0;
    while n != 0 {
        // This clears the least significant bit
        n = n & (n - 1);
        count += 1;
    }
    count
}
}

Why it's better: The number of loop iterations is equal to the number of set bits. This is much faster for "sparse" numbers (numbers with few '1's). For the worst case (0xFFFFFFFF), it performs 32 iterations, but on average, it's much faster.

2. Lookup Table (LUT)

This method trades memory for speed. We can pre-calculate the Hamming weight for every possible 8-bit number (a byte) and store it in an array. Then, we can process a 32-bit integer as four separate 8-bit chunks.

The Code:

#![allow(unused)]
fn main() {
// Pre-generate this table once
const BITS_IN_BYTE: [i32; 256] = {
    let mut table = [0; 256];
    let mut i = 0;
    while i < 256 {
        // Using the Kernighan algorithm to generate the table entries
        let mut n = i;
        let mut count = 0;
        while n > 0 {
            n &= n - 1;
            count += 1;
        }
        table[i] = count;
        i += 1;
    }
    table
};

fn hamming_weight_lut(n: u32) -> i32 {
    // Break the 32-bit integer into four 8-bit bytes and sum their weights
    BITS_IN_BYTE[(n & 0xff) as usize] +
    BITS_IN_BYTE[((n >> 8) & 0xff) as usize] +
    BITS_IN_BYTE[((n >> 16) & 0xff) as usize] +
    BITS_IN_BYTE[((n >> 24) & 0xff) as usize]
}
}

Why it's better: This is extremely fast. It has no loops or branches, just a few bitwise operations, four array lookups, and three additions. Its performance is constant regardless of the input. The main downside is the memory cost of the lookup table (256 bytes in this case).

3. Parallel Bit-Counting (SWAR)

This is a "bit-twiddling hack" that computes the Hamming weight in parallel. It works by treating the 32-bit integer as a vector of smaller fields and adding them up simultaneously (SWAR stands for "SIMD Within A Register").

How it works (conceptual):

1. Count set bits in adjacent 2-bit chunks.
2. Sum the results into 4-bit chunks.
3. Sum the results into 8-bit chunks.
4. Sum the results into 16-bit chunks.
5. Sum the final results into a 32-bit chunk.

The "magic numbers" are masks used to prevent the sums from overflowing into the next chunk.

The Code:

#![allow(unused)]
fn main() {
fn hamming_weight_parallel(mut n: u32) -> i32 {
    // Step 1: Count bits in 2-bit chunks (result in each chunk is 0, 1, or 2)
    // 0x55555555 is 01010101...
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555);

    // Step 2: Sum 2-bit chunk results into 4-bit chunks (max result 4)
    // 0x33333333 is 00110011...
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);

    // Step 3: Sum 4-bit chunk results into 8-bit chunks (max result 8)
    // 0x0F0F0F0F is 00001111...
    n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);

    // Step 4: Sum 8-bit chunk results into 16-bit chunks (max result 16)
    // 0x00FF00FF is 0000000011111111...
    n = (n & 0x00FF00FF) + ((n >> 8) & 0x00FF00FF);

    // Step 5: Sum 16-bit chunk results into a 32-bit chunk (max result 32)
    // 0x0000FFFF is 00000000000000001111111111111111
    n = (n & 0x0000FFFF) + ((n >> 16) & 0x0000FFFF);

    n as i32
}
}

Why it's better: Like the lookup table, this is a branchless, loop-free algorithm with constant-time performance. It uses no extra memory. This is often how standard library implementations of count_ones() are written for architectures that lack a dedicated hardware instruction.

Conclusion: Why n.count_ones() is the Actual Best Solution

You are right to be aware of n.count_ones(). For any real-world code, it is the superior choice for three key reasons:

1. Hardware Intrinsics: Most modern CPUs (like x86 and ARM) have a single, highly-optimized machine instruction to count set bits (e.g., POPCNT, VCNT). The Rust compiler is smart enough to translate n.count_ones() directly into that single instruction. None of the algorithms above can beat a dedicated hardware instruction that runs in 1-3 clock cycles.

2. Optimal Fallback: On the rare occasion that the target CPU doesn't have a POPCNT instruction, the Rust standard library will use a heavily optimized fallback, typically a variation of the parallel (SWAR) or lookup table method. You get the best possible implementation for your target architecture automatically.

3. Readability and Maintainability: Code should be as clear as possible. n.count_ones() perfectly describes its intent. The other algorithms, while clever, are harder to read and understand at a glance.

Summary Table

Optimizing a Rust Substitution Cipher Implementation

The Question

I have the following Rust code that implements a substitution cipher. The key string is used to build a substitution map, and then the message is decoded using that map. Can this code be made better?

Original Code

#![allow(unused)]
fn main() {
use std::collections::HashMap;

fn decode(key: String, message: String) -> String {
    let mut map: HashMap<char, char> = HashMap::new();
    map.insert(' ', ' ');
    let mut mapped_c = 'a';
    for ch in key.chars() {
        if ch != ' ' && !map.contains_key(&ch) {
            map.insert(ch, mapped_c);
            mapped_c = ((mapped_c as u8) + 1) as char;
        }
    }
    let mut result = String::new();
    for ch in message.chars() {
        if let Some(ch_mapped) = map.get(&ch) {
            result.push(*ch_mapped);
        }
    }
    result
}
}

The Answer

Excellent question. Yes, this code can definitely be improved in terms of performance, readability, and idiomatic Rust.

Your current code is clear and correctly implements a substitution cipher based on the first appearance of characters in a key. However, it has a few areas for optimization.

Let's break down the improvements.

1. Idiomatic Rust & Readability Improvements

Use the entry API

Instead of checking !map.contains_key(&ch) and then inserting, you can use the entry API. This is more efficient as it only performs one lookup in the map, and it's considered more idiomatic.

#![allow(unused)]
fn main() {
// Your original code
if ch != ' ' && !map.contains_key(&ch) {
    map.insert(ch, mapped_c);
    mapped_c = ((mapped_c as u8) + 1) as char;
}

// Using the entry API
use std::collections::hash_map::Entry;

if ch != ' ' {
    if let Entry::Vacant(v) = map.entry(ch) {
        v.insert(mapped_c);
        mapped_c = ((mapped_c as u8) + 1) as char;
    }
}
}

This ensures the logic for checking and inserting is an atomic operation and is generally cleaner.

2. Performance Improvements

Pre-allocating the Result String

You are building the result string by pushing one character at a time. Each time the string's capacity is exceeded, Rust has to allocate a new, larger block of memory and copy the old content over. You can avoid this by pre-allocating the string with the right capacity.

#![allow(unused)]
fn main() {
// Before
let mut result = String::new();

// After: Guarantees only one memory allocation for the string
let mut result = String::with_capacity(message.len());
}

Using an Array as a Lookup Table (Major Improvement)

A HashMap is a powerful, general-purpose tool. However, when your keys are chars (especially if you can assume they are ASCII), using an array as a direct lookup table is significantly faster.

• Why? Accessing an array element by its index (map[i]) is a direct memory lookup (O(1) with a very small constant factor). A HashMap lookup involves hashing the key, finding the right bucket, and potentially checking for collisions (average O(1) but with a much larger constant factor).

Let's assume the characters are within the ASCII range (0-127). We can create an array of size 128 to store the mappings.

The Refactored Solution

This version incorporates the performance improvements. It's much faster for typical inputs because it avoids all hashing and uses a simple array lookup.

#![allow(unused)]
fn main() {
fn decode_message(key: &str, message: &str) -> String {
    // 1. Use an array as a faster lookup table for ASCII characters.
    // Initialize with a sentinel value (0) to indicate "not mapped yet".
    let mut map = [0u8; 128];

    // Map space to itself.
    map[b' ' as usize] = b' ';

    // 2. Use `b'a'` for byte literals, which is slightly more efficient.
    let mut current_char = b'a';

    // 3. Build the mapping table.
    for &byte in key.as_bytes() {
        // We only care about characters that haven't been mapped yet.
        if byte != b' ' && map[byte as usize] == 0 {
            map[byte as usize] = current_char;
            current_char += 1;
        }
    }

    // 4. Pre-allocate the result string for a single allocation.
    let mut result = String::with_capacity(message.len());

    // 5. Decode the message using the fast array lookup.
    for &byte in message.as_bytes() {
        // The map contains the substitution if it was in the key, or 0 otherwise.
        // The original code skipped characters not in the map, so we do the same.
        let mapped_char = map[byte as usize];
        if mapped_char != 0 {
             result.push(mapped_char as char);
        }
    }

    result
}
}

Summary of Improvements

For most competitive programming and performance-critical scenarios involving character substitution, the array-based lookup table is the superior solution.