Skip to content
TheChatArchiveThe Chat Archive
Geminigemini-2.5-pro-exp-03-25-grounding· GoogleHugging Face LMArena Search Arena 24K

Write lcs code in Rust

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with gpt-4o-search-preview-high’s answer.
  1. User

    Write lcs code in Rust

  2. Gemini Assistant

    Okay, here's the Rust code to find the Longest Common Subsequence (LCS) of two strings using dynamic programming. This code will provide both the length of the LCS and the LCS string itself.

    use std::cmp;
    use std::io;
    
    // Function to find the length of the Longest Common Subsequence (LCS)
    fn lcs_length(s1: &str, s2: &str) -> usize {
        let chars1: Vec<char> = s1.chars().collect();
        let chars2: Vec<char> = s2.chars().collect();
        let m = chars1.len();
        let n = chars2.len();
    
        // Create a DP table (matrix) to store lengths of LCSs.
        // dp[i][j] will contain the length of LCS of s1[0..i-1] and s2[0..j-1]
        let mut dp = vec![vec![0; n + 1]; m + 1];
    
        // Build the dp table in bottom-up fashion
        for i in 1..=m {
            for j in 1..=n {
                if chars1[i - 1] == chars2[j - 1] {
                    // If characters match, LCS length increases by 1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // If characters don't match, take the max length from the previous row or column
                    dp[i][j] = cmp::max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
    
        // The bottom-right cell contains the length of LCS for the entire strings
        dp[m][n]
    }
    
    // Function to find the actual Longest Common Subsequence (LCS) string
    fn lcs_string(s1: &amp;str, s2: &amp;str) -&gt; String {
        let chars1: Vec<char> = s1.chars().collect();
        let chars2: Vec<char> = s2.chars().collect();
        let m = chars1.len();
        let n = chars2.len();
    
        // Create the DP table same as in lcs_length
        let mut dp = vec![vec![0; n + 1]; m + 1];
        for i in 1..=m {
            for j in 1..=n {
                if chars1[i - 1] == chars2[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = cmp::max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
    
        // Backtrack from dp[m][n] to reconstruct the LCS string
        let mut lcs = String::new();
        let mut i = m;
        let mut j = n;
    
        while i &gt; 0 &amp;&amp; j &gt; 0 {
            // If current characters match, they are part of LCS
            if chars1[i - 1] == chars2[j - 1] {
                lcs.push(chars1[i - 1]);
                i -= 1;
                j -= 1;
            }
            // If characters don't match, move in the direction of the larger LCS length
            else if dp[i - 1][j] &gt; dp[i][j - 1] {
                i -= 1;
            } else {
                j -= 1;
            }
        }
    
        // The LCS string is built backwards, so reverse it
        lcs.chars().rev().collect()
    }
    
    
    fn main() {
        let mut s1 = String::new();
        let mut s2 = String::new();
    
        println!("Enter the first string:");
        io::stdin().read_line(&amp;mut s1).expect("Failed to read line");
        let s1 = s1.trim(); // Remove trailing newline
    
        println!("Enter the second string:");
        io::stdin().read_line(&amp;mut s2).expect("Failed to read line");
        let s2 = s2.trim(); // Remove trailing newline
    
        println!("\nString 1: {}", s1);
        println!("String 2: {}", s2);
    
        let length = lcs_length(s1, s2);
        println!("\nLength of the Longest Common Subsequence: {}", length);
    
        let sequence = lcs_string(s1, s2);
        println!("The Longest Common Subsequence is: \"{}\"", sequence);
    
        // --- Example Test Cases ---
        println!("\n--- Example Test Cases ---");
    
        let str1 = "AGGTAB";
        let str2 = "GXTXAYB";
        println!("\nStrings: \"{}\", \"{}\"", str1, str2);
        println!("LCS Length: {}", lcs_length(str1, str2)); // Expected: 4
        println!("LCS String: \"{}\"", lcs_string(str1, str2)); // Expected: "GTAB"
    
        let str3 = "ABCBDAB";
        let str4 = "BDCAB";
        println!("\nStrings: \"{}\", \"{}\"", str3, str4);
        println!("LCS Length: {}", lcs_length(str3, str4)); // Expected: 4
        println!("LCS String: \"{}\"", lcs_string(str3, str4)); // Expected: "BCAB" or "BDAB" (depends on tie-breaking in backtracking)
    
        let str5 = "ABCD";
        let str6 = "AEBD";
        println!("\nStrings: \"{}\", \"{}\"", str5, str6);
        println!("LCS Length: {}", lcs_length(str5, str6)); // Expected: 3
        println!("LCS String: \"{}\"", lcs_string(str5, str6)); // Expected: "ABD"
    
         let str7 = "ABC";
         let str8 = "DEF";
         println!("\nStrings: \"{}\", \"{}\"", str7, str8);
         println!("LCS Length: {}", lcs_length(str7, str8)); // Expected: 0
         println!("LCS String: \"{}\"", lcs_string(str7, str8)); // Expected: ""
    
         let str9 = "";
         let str10 = "XYZ";
         println!("\nStrings: \"{}\", \"{}\"", str9, str10);
         println!("LCS Length: {}", lcs_length(str9, str10)); // Expected: 0
         println!("LCS String: \"{}\"", lcs_string(str9, str10)); // Expected: ""
    }
    

    Explanation:

    1. lcs_length function:

      • Takes two string slices (&amp;str) as input.
      • Converts them into Vec<char> to handle Unicode characters correctly and allow easy indexing.
      • Initializes a 2D vector dp of size (m+1) x (n+1) with zeros, where m and n are the lengths of the input strings. dp[i][j] will store the LCS length for the first i chars of s1 and the first j chars of s2.
      • Iterates through the strings (using 1-based indexing for the dp table) and fills the table based on the standard LCS recurrence relation:
        • If chars1[i-1] == chars2[j-1], the LCS length increases by 1 from the diagonal element: dp[i][j] = dp[i-1][j-1] + 1.
        • If characters don't match, the LCS length is the maximum of the lengths obtained by excluding the last character of s1 (dp[i-1][j]) or the last character of s2 (dp[i][j-1]).
      • Finally, returns dp[m][n], which holds the LCS length for the complete strings.
    2. lcs_string function:

      • Starts similarly to lcs_length by calculating the dp table.
      • After the table is filled, it reconstructs the actual LCS string by backtracking from the bottom-right cell (dp[m][n]).
      • It uses indices i and j, starting at m and n.
      • In a loop (while i &gt; 0 &amp;&amp; j &gt; 0):
        • If chars1[i-1] == chars2[j-1], it means this character is part of the LCS. It's appended to the lcs string (which is built in reverse), and both i and j are decremented.
        • If the characters don't match, it checks which cell (dp[i-1][j] or dp[i][j-1]) contributed to the maximum length stored in dp[i][j]. It then moves i or j accordingly (up or left in the conceptual grid). If both are equal, it arbitrarily chooses one direction (here, it prefers moving left by default).
      • Since the LCS string is built by appending characters from the end, the resulting lcs string needs to be reversed before being returned.
    3. main function:

      • Prompts the user to enter two strings.
      • Calls lcs_length and lcs_string to get the results.
      • Prints the length and the sequence.
      • Includes several hardcoded examples to demonstrate functionality.

    This code provides a standard and efficient way to compute the LCS in Rust.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.