3330. Find the Original Typed String I

Time: O(n)

Space: O(1)

Intuition

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

Algorithm

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

// 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?