1750. Minimum Length of String After Deleting Similar Ends Medium

1/**
2 * [1750] Minimum Length of String After Deleting Similar Ends
3 *
4 * Given a string s consisting only of characters 'a', 'b', and 'c'. You are asked to apply the following algorithm on the string any number of times:
5 * <ol>
6 * 	Pick a non-empty prefix from the string s where all the characters in the prefix are equal.
7 * 	Pick a non-empty suffix from the string s where all the characters in this suffix are equal.
8 * 	The prefix and the suffix should not intersect at any index.
9 * 	The characters from the prefix and suffix must be the same.
10 * 	Delete both the prefix and the suffix.
11 * </ol>
12 * Return the minimum length of s after performing the above operation any number of times (possibly zero times).
13 *  
14 * Example 1:
15 * 
16 * Input: s = "ca"
17 * Output: 2
18 * Explanation: You can't remove any characters, so the string stays as is.
19 * 
20 * Example 2:
21 * 
22 * Input: s = "cabaabac"
23 * Output: 0
24 * Explanation: An optimal sequence of operations is:
25 * - Take prefix = "c" and suffix = "c" and remove them, s = "abaaba".
26 * - Take prefix = "a" and suffix = "a" and remove them, s = "baab".
27 * - Take prefix = "b" and suffix = "b" and remove them, s = "aa".
28 * - Take prefix = "a" and suffix = "a" and remove them, s = "".
29 * Example 3:
30 * 
31 * Input: s = "aabccabba"
32 * Output: 3
33 * Explanation: An optimal sequence of operations is:
34 * - Take prefix = "aa" and suffix = "a" and remove them, s = "bccabb".
35 * - Take prefix = "b" and suffix = "bb" and remove them, s = "cca".
36 * 
37 *  
38 * Constraints:
39 * 
40 * 	1 <= s.length <= 10^5
41 * 	s only consists of characters 'a', 'b', and 'c'.
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/minimum-length-of-string-after-deleting-similar-ends/
47// discuss: https://leetcode.com/problems/minimum-length-of-string-after-deleting-similar-ends/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn minimum_length(s: String) -> i32 {
53        0
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_1750() {
65    }
66}
67