DDSA Solutions

3330. Find the Original Typed String I

EasyView on LeetCode
StringCounting
Time: O(n)
Space: O(1)

Problem Overview

Find lexicographically smallest string after removing one character.

Intuition

Find lexicographically smallest string after removing one character. Remove the first character where the next is smaller or equal.

Algorithm

  1. 1Scan left to right. Remove first i where s[i] >= s[i+1]. If none: remove last.

Common Pitfalls

  • •For strictly decreasing string: remove last character. Otherwise: remove first descent point.
3330.cs
C#
// Approach: Count consecutive run lengths > 1; each contributes one extra possible original string.
// Time: O(n) Space: O(1)

public class Solution
{
    public int PossibleStringCount(string word)
    {
        int count = 1; // Initialize the count to 1 because the first character is always counted
        // Loop through the string starting from the second character
        for (int i = 1; i < word.Length; ++i)
        {
            // Check if the current character is the same as the previous one
            if (word[i] == word[i - 1])
                ++count; // Increment the count if characters are the same
        }
        return count; // Return the total count of adjacent duplicate characters
    }
}
Was this solution helpful?

Related Problems