Rust Example

use std::iter::FromIterator;
use std::collections::{HashMap, HashSet};


/// Returns the largest string from doing the allowed swaps.
///
/// Given a string `string` and `array` of pairs that indicates which
/// indices in the string can be swapped, return the lexicographically
/// largest string that results from doing the allowed swaps. You can
/// swap indices any number of times.
///
/// # Example
///
/// ```
/// let string = String::from("abdc");
/// let pairs = vec![vec![1, 4], vec![3, 4]];
/// let expected = String::from("dbca");
///
/// assert_eq!(swapLexOrder(string, pairs), expected);
/// ```
fn swapLexOrder(mut string: String, pairs: Vec<Vec<i32>>) -> String {
    let index_to_char = stringIndicesToChar(&string);
    let connected_components = connectedPairComponents(&pairs);

    for component in &connected_components {
        let mut lex_sorted = component
            .iter()
            .map(|index| index_to_char[&index])
            .collect::<Vec<char>>();

        lex_sorted.sort_by(|a, b| b.cmp(a));

        placeCharsAtIndicesInString(&mut string, component, &lex_sorted);
    }

    string
}


/// Returns the map of indices to chars from a string.
///
/// # Example
///
/// ```
/// use std::collections::HashMap;
///
/// let string = String::from("abdc");
/// let mut expected = HashMap::new();
///
/// expected.insert(1, 'a');
/// expected.insert(2, 'b');
/// expected.insert(3, 'd');
/// expected.insert(4, 'c');

///
/// assert_eq!(stringIndicesToChar(&string), expected);
/// ```
fn stringIndicesToChar(string: &str) -> HashMap<i32, char> {
    let mut index_to_char = HashMap::new();

    for (index, ch) in string.char_indices() {
        index_to_char.insert(index as i32 + 1, ch);
    }

    index_to_char
}


/// Places chars at the given indices of a string.
///
/// # Example
///
/// ```
/// let mut string = String::from("abdc");
/// let indices = vec![1, 3, 4];
/// let chars = vec!['d', 'c', 'a'];
/// let expected = String::from("dbca");
///
/// assert_eq!(
///     placeCharsAtIndicesInString(&mut string, &indices, &chars),
///     expected);
/// ```
fn placeCharsAtIndicesInString(string: &mut String,
                               indicies: &Vec<i32>,
                               chars: &Vec<char>) {
    let mut new_string = string.chars().collect::<Vec<char>>();

    for (index, ch) in indicies.iter().zip(chars.iter()) {
        new_string[*index as usize - 1] = *ch;
    }

    *string = new_string.into_iter().collect::<String>();
}


/// Returns the connected compenents from a given vector of pairs.
///
/// # Example
///
/// ```
/// let pairs = vec![vec![0, 2],
///                  vec![5, 7],
///                  vec![7, 2],
///                  vec![1, 6]];
/// let expected = vec![vec![0, 2, 5, 7], vec![1, 6]];
/// let mut to_test = connectedPairComponents(&pairs);
///
/// to_test.sort();
///
/// assert_eq!(to_test, expected);
/// ```
fn connectedPairComponents(pairs: &Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let mut seen = HashSet::new();
    let mut connected_components = Vec::new();

    for pair in pairs {
        if !seen.contains(pair) {
            let mut connections = Vec::from_iter(
                connectedPairsDFS(pair, pairs, &mut seen));

            connections.sort();

            connected_components.push(Vec::from_iter(connections));
        }
    }

    connected_components
}


/// Returns the connect pairs to a given pair using DFS.
///
/// # Example
///
/// ```
/// use std::iter::FromIterator;
/// use std::collections::HashSet;
///
/// let mut seen = HashSet::new();
/// let pair = vec![0, 2];
/// let pairs = vec![vec![0, 2],
///                  vec![5, 7],
///                  vec![7, 2],
///                  vec![1, 6]];
/// let expected = HashSet::from_iter(
///     [0, 2, 5, 7].into_iter());

///
/// assert_eq!(
///     connectedPairsDFS(&pair, &pairs, &mut seen),
///     expected);
/// ```
fn connectedPairsDFS(pair: &Vec<i32>,
                     pairs: &Vec<Vec<i32>>,
                     seen: &mut HashSet<Vec<i32>>)
                     -> HashSet<i32> {
    let mut connections = HashSet::from_iter(pair.clone());

    if !seen.insert(pair.clone()) {
        return connections;
    }

    for other_pair in pairs {
        if areConnected(pair, other_pair) && (other_pair != pair) {
            connections.extend(connectedPairsDFS(other_pair, pairs, seen));
        }
    }

    connections
}


/// Indicates whether two pairs are connected.
///
/// # Example
///
/// ```
/// assert!(are_connected(&vec![0, 2], &vec![7, 2]);
/// assert!(!are_connected(&vec[0, 2], &vec![5, 7]);
/// ```
fn areConnected(first_pair: &Vec<i32>, second_pair: &Vec<i32>) -> bool {
   first_pair.contains(&second_pair[0]) || first_pair.contains(&second_pair[1])
}