DEV Community

Cover image for 3223. Minimum Length of String After Operations
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

3223. Minimum Length of String After Operations

3223. Minimum Length of String After Operations

Difficulty: Medium

Topics: Hash Table, String, Counting

You are given a string s.

You can perform the following process on s any number of times:

  • Choose an index i in the string such that there is at least one character to the left of index i that is equal to s[i], and at least one character to the right that is also equal to s[i].
  • Delete the closest character to the left of index i that is equal to s[i].
  • Delete the closest character to the right of index i that is equal to s[i].

Return the minimum length of the final string s that you can achieve.

Example 1:

  • Input: s = "abaacbcbb"
  • Output: 5
  • Explanation: We do the following operations:
    • Choose index 2, then remove the characters at indices 0 and 3. The resulting string is s = "bacbcbb".
    • Choose index 3, then remove the characters at indices 0 and 5. The resulting string is s = "acbcb".

Example 2:

  • Input: s = "aa"
  • Output: 2
  • Explanation: We cannot perform any operations, so we return the length of the original string.

Constraints:

  • 1 <= s.length <= 2 * 105
  • s consists only of lowercase English letters.

Hint:

  1. Only the frequency of each character matters in finding the final answer.
  2. If a character occurs less than 3 times, we cannot perform any process with it.
  3. Suppose there is a character that occurs at least 3 times in the string, we can repeatedly delete two of these characters until there are at most 2 occurrences left of it.

Solution:

We need to focus on the frequency of each character in the string. Here’s the approach to solve it:

Approach:

  1. Count Character Frequencies:

    • Use a frequency table to count how many times each character appears in the string.
  2. Reduce Characters with Frequency >= 3:

    • If a character appears 3 or more times, we can repeatedly delete two of them until only 2 occurrences are left.
  3. Calculate the Minimum Length:

    • Sum up the remaining counts of all characters after reducing the frequencies.

Let's implement this solution in PHP: 3223. Minimum Length of String After Operations

<?php
/**
 * @param String $s
 * @return Integer
 */
function minimumLength($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$s1 = "abaacbcbb";
echo "Input: $s1\n";
echo "Output: " . minimumLength($s1) . "\n";

// Example 2
$s2 = "aa";
echo "Input: $s2\n";
echo "Output: " . minimumLength($s2) . "\n";
?>
Enter fullscreen mode Exit fullscreen mode

Explanation:

  1. Frequency Count:

    • Iterate through the string, and for each character, increment its count in the $frequency array.
  2. Reduction of Characters:

    • For each character in the $frequency array, check if its count is 3 or more. If so, reduce it to at most 2.
  3. Calculate the Result:

    • Sum the values in the $frequency array to get the minimum possible length of the string.

Example Walkthrough:

Example 1:

  • Input: s = "abaacbcbb"
  • Frequencies: ['a' => 3, 'b' => 4, 'c' => 2]
  • After reduction:
    • 'a' => 2 (reduced from 3),
    • 'b' => 2 (reduced from 4),
    • 'c' => 2 (no reduction needed).
  • Minimum length: 2 + 2 + 2 = 6.

Example 2:

  • Input: s = "aa"
  • Frequencies: ['a' => 2]
  • No reduction needed since no character has a frequency of 3 or more.
  • Minimum length: 2.

Complexity:

  1. Time Complexity:

    • Counting frequencies: O(n), where n is the length of the string.
    • Reduction: O(1) (constant time, as there are only 26 lowercase letters).
    • Summing frequencies: O(1).
    • Overall: O(n).
  2. Space Complexity:

    • O(1), since the frequency array has at most 26 entries.

This solution is efficient and works well within the problem's constraints.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay