Package g1701_1800.s1750_minimum_length_of_string_after_deleting_similar_ends

Class Solution

java.lang.Object

g1701_1800.s1750_minimum_length_of_string_after_deleting_similar_ends.Solution

public class Solution
extends Object

1750 - Minimum Length of String After Deleting Similar Ends.<p>Medium</p> <p>Given a string <code>s</code> consisting only of characters <code>'a'</code>, <code>'b'</code>, and <code>'c'</code>. You are asked to apply the following algorithm on the string any number of times:</p> <ol> <li>Pick a <strong>non-empty</strong> prefix from the string <code>s</code> where all the characters in the prefix are equal.</li> <li>Pick a <strong>non-empty</strong> suffix from the string <code>s</code> where all the characters in this suffix are equal.</li> <li>The prefix and the suffix should not intersect at any index.</li> <li>The characters from the prefix and suffix must be the same.</li> <li>Delete both the prefix and the suffix.</li> </ol> <p>Return <em>the <strong>minimum length</strong> of</em> <code>s</code> <em>after performing the above operation any number of times (possibly zero times)</em>.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> s = &ldquo;ca&rdquo;</p> <p><strong>Output:</strong> 2</p> <p><strong>Explanation:</strong> You can&rsquo;t remove any characters, so the string stays as is.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> s = &ldquo;cabaabac&rdquo;</p> <p><strong>Output:</strong> 0</p> <p><strong>Explanation:</strong> An optimal sequence of operations is:</p> <ul> <li> <p>Take prefix = &ldquo;c&rdquo; and suffix = &ldquo;c&rdquo; and remove them, s = &ldquo;abaaba&rdquo;.</p> </li> <li> <p>Take prefix = &ldquo;a&rdquo; and suffix = &ldquo;a&rdquo; and remove them, s = &ldquo;baab&rdquo;.</p> </li> <li> <p>Take prefix = &ldquo;b&rdquo; and suffix = &ldquo;b&rdquo; and remove them, s = &ldquo;aa&rdquo;.</p> </li> <li> <p>Take prefix = &ldquo;a&rdquo; and suffix = &ldquo;a&rdquo; and remove them, s = &quot;&quot;.</p> </li> </ul> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> s = &ldquo;aabccabba&rdquo;</p> <p><strong>Output:</strong> 3</p> <p><strong>Explanation:</strong> An optimal sequence of operations is:</p> <ul> <li> <p>Take prefix = &ldquo;aa&rdquo; and suffix = &ldquo;a&rdquo; and remove them, s = &ldquo;bccabb&rdquo;.</p> </li> <li> <p>Take prefix = &ldquo;b&rdquo; and suffix = &ldquo;bb&rdquo; and remove them, s = &ldquo;cca&rdquo;.</p> </li> </ul> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= s.length <= 10⁵</code></li> <li><code>s</code> only consists of characters <code>'a'</code>, <code>'b'</code>, and <code>'c'</code>.</li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	minimumLength(String s)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

minimumLength

public int minimumLength(String s)