Delete Characters To Make Fancy String - Leetcode Solution

Problem Statement:

Given a string s consisting of lowercase Latin letters and spaces, your task is to remove the spaces and create a fancy string with the characters of s.

A fancy string is a string where no two adjacent characters are equal. For example, "aba" is not a fancy string because the two adjacent a's are equal, but "ab" is a fancy string because there are no adjacent equal characters.

Return the fancy string that you can obtain by deleting the spaces and replacing the spaces with nothing.

Example 1:

Input: s = "hello world" Output: "heloworld"

Example 2:

Input: s = "h el lo" Output: "hello"

Solution:

We can solve this problem by iterating through the string and appending all the non-space characters to a new string while checking that no two adjacent characters are equal.

Algorithm:

1. Define an empty string fancyStr to store the result.
2. Set a variable lastChar to an empty string to store the last character appended to fancyStr.
3. Loop through each character c in the input string s.
4. If c is not a space and is not equal to the last character in fancyStr, append c to fancyStr and update lastChar to c.
5. Return fancyStr.

Code:

Here is the Python code to solve this problem:

class Solution: def makeFancyString(self, s: str) -> str: fancyStr = '' lastChar = '' for c in s: if c != ' ' and c != lastChar: fancyStr += c lastChar = c return fancyStr

Complexity Analysis:

Time Complexity: O(n), where n is the length of the input string s. We iterate through each character of the string at most once.

Space Complexity: O(n), for storing the output string of length n.

1