Problem: Alternating Characters CleanupDescription
You are given a string s consisting only of the characters 'A' and 'B'. You want to make the string "good" by deleting the minimum number of characters such that no two adjacent characters are the same.
A "good" string is one where no two adjacent characters are equal.
Your task is to find the minimum number of deletions required.
Input Format
A single line containing the string s (1 ≤ len(s) ≤ 1000), consisting only of A and B.
Output Format
An integer denoting the minimum number of deletions required.
Sample Input 1
AABAAB
Sample Output 1
2
Sample Input 2
ABABAB
Sample Output 2
0
Explanation
In the first example, one possible "good" string is ABAB, which takes 2 deletions.
In the second example, the string already alternates correctly, so no deletions are needed.
Possible Solution
s = "afafasgggewrtdg"
min_deletions = 0
last_seen_character = None
for c in s:
if c == last_seen_character:
min_deletions += 1
last_seen_character = c
print(min_deletions)
Complexity
Time: O(n) — one pass through the string
Space: O(1) — only a couple of counters
Problem: Longest Nice Substring
A string is considered "nice" if it contains equal numbers of vowels and consonants, and all characters are lowercase English letters.
You are given a lowercase string s. Find the length of the longest contiguous "nice" substring.
Input
A single string s consisting of only lowercase English letters.
1 <= len(s) <= 1000
Output
Print the length of the longest "nice" substring in s.
ExampleInput
abcdeiou
Output
6
~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~
Can you ask me a (that may be simple at rating of about 4/10) coding problem that tests problem solving skills of the candidate?
Absolutely! Here's a simple but insightful (4/10 difficulty) coding problem that tests:
Basic string manipulation
Loop logic
Attention to detail in pattern detection
🔹 Problem: Longest Nice Substring
A string is considered "nice" if it contains equal numbers of vowels and consonants, and all characters are lowercase English letters.
You are given a lowercase string s. Find the length of the longest contiguous "nice" substring.
🧪 Input
A single string s consisting of only lowercase English letters. 1 <= len(s) <= 1000
📤 Output
Print the length of the longest "nice" substring in s.
🧾 Example
Input:
nginx
abcdeiou
Output:
6
Explanation:
The substring cdeiou has 3 consonants (c, d, e) and 3 vowels (i, o, u) → hence it's "nice".
Its length is 6.
🎯 What this tests:
Understanding of substrings
Frequency counting
Sliding window or brute-force optimization
Would you like a follow-up version that increases difficulty slightly (e.g., rating 6/10) by adding mixed-case handling or requiring lexicographically smallest nice substring?
can you share it's solution?
Certainly! Here's a straightforward solution using brute-force with optimizations, suitable for a 4/10 difficulty level.
✅ Solution Explanation
Iterate over all possible substrings of the given string s.
For each substring:
Count the number of vowels and consonants.
If both are equal, it's a "nice" substring.
Track the maximum length found.
Since the max length of s is 1000, a brute-force approach with substring checks is still acceptable for small inputs.
🧠 Python Code
python
defis_vowel(ch):
return ch in'aeiou'deflongest_nice_substring(s):
n = len(s)
max_len = 0for i inrange(n):
vowels = 0
consonants = 0for j inrange(i, n):
if is_vowel(s[j]):
vowels += 1else:
consonants += 1if vowels == consonants:
max_len = max(max_len, j - i + 1)
return max_len
# Example usage
s = input().strip()
print(longest_nice_substring(s))
📈 Time Complexity
Worst-case: O(n²) — due to checking all substrings.
But inner loop operations are O(1), making it acceptable for n ≤ 1000.
🧪 Test Example
Input:
nginx
abcdeiou
Output:
6
Nice substring: cdeiou
Would you like a more optimized version using prefix sums or a sliding window?
Yes, please share the optimized solution
Great! Here's an optimized solution using prefix sums and hash maps to reduce the time complexity from O(n²) to approximately O(n).
✅ Optimized Approach: Prefix Sum + Hash Map
We treat:
vowel as +1
consonant as -1
We compute a running sum. If the same value has occurred before, then the substring in between has an equal number of vowels and consonants.
🧠 Python Code (Optimized):
python
defis_vowel(ch):
return ch in'aeiou'deflongest_nice_substring(s):
n = len(s)
prefix_sum = 0
index_map = {0: -1} # sum -> earliest index
max_len = 0for i inrange(n):
if is_vowel(s[i]):
prefix_sum += 1else:
prefix_sum -= 1if prefix_sum in index_map:
max_len = max(max_len, i - index_map[prefix_sum])
else:
index_map[prefix_sum] = i
return max_len
# Example usage
s = input().strip()
print(longest_nice_substring(s))
📈 Time and Space Complexity:
Time:O(n)
Space:O(n) (for the hashmap)
🧪 Example
Input:
nginx
aeiobcdfg
Output:
8
Explanation: eiobcdfg contains 4 vowels and 4 consonants.
Let me know if you'd like to extend this to handle uppercase, or allow more fine-tuned constraints like ignoring non-alphabetic characters.
Can you pls breakdown and explain this solution?
Absolutely! Let's break down the optimized solution step-by-step so you understand the logic and mechanics clearly.
🔁 Problem Recap
You are given a string of lowercase letters, and you must find the length of the longest substring that contains an equal number of vowels and consonants.
✅ Key Insight:
We convert this into a running balance problem:
Every vowel is treated as +1
Every consonant is treated as -1
Now the goal becomes:
👉 Find the longest substring where the total balance is zero, i.e., the number of vowels and consonants are equal.
Problem: Remove Consecutive Duplicates
Given a string s, remove all consecutive duplicate characters and return the resulting string.
Input Format
A single line containing a string s (1 ≤ length of s ≤ 1000)
The string will contain only lowercase English letters.
Output Format
Print the string after removing consecutive duplicate characters.
Sample Input 1
aabbccddeee
Sample Output 1
abcde
Sample Input 2
aabaaabb
Sample Output 2
abab
~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~
Can you ask me a (that may be simple at rating of about 3/10) coding problem that tests problem solving skills of the candidate?
Sure! Here's a simple (3/10 difficulty) coding problem that tests basic problem-solving, string handling, and logic skills:
✅ Problem: Remove Consecutive Duplicates
Given a string s, remove all consecutive duplicate characters and return the resulting string.
🔹 Input Format
A single line containing a string s (1 ≤ length of s ≤ 1000)
The string will contain only lowercase English letters.
🔹 Output Format
Print the string after removing consecutive duplicate characters.
🔹 Sample Input 1
nginx
aabbccddeee
🔹 Sample Output 1
nginx
abcde
🔹 Sample Input 2
nginx
aabaaabb
🔹 Sample Output 2
nginx
abab
🧠 What it tests
Understanding of string traversal
Use of conditionals
Handling edge cases like repeated or single characters
Let me know when you're ready for the solution or hints!
Can you critique this rough algo:
s = "afafasgggewrtdg"
t = ""
last_seen_character = ''
streak_found = False
for c in s:
if c not in t:
t += c
last_seen_character = c
elif c in t and last_seen_character == c:
streak_found = True
last_seen_character = c
continue
else (c in t) and last_seen_character != c and not streak_found:
t += c
last_seen_character = c
streak_found = False
Thanks for sharing your rough algorithm! You're clearly thinking through the logic and edge cases, which is great. Let’s break down the approach and evaluate it step by step.
🔍 Your Goal:
You want to remove consecutive duplicate characters from a string.
Use of flags: You introduced streak_found to handle streaks, though it's a bit more complex than needed for this problem.
Good intent: You’re trying to avoid adding characters that have already been added if they’re part of a consecutive streak.
❌ Issues in the Logic:
Wrong check for character presence in t:
You’re checking if c not in t, but this checks if the character has ever occurred in t, not if it's the same as the previous one.
This can cause issues with strings like "aabaaabb" — you'll incorrectly skip valid characters.
Incorrect else condition:
Python syntax error: else (c in t) and ... is invalid.
else doesn’t take a condition. You’d need to use elif again.
Unnecessary use of streak_found:
You don’t need a streak_found flag. You only need to compare each character to the one immediately before it.
Adding characters that are not duplicates but previously seen:
You're preventing characters from being added again even if they're not consecutive — which is incorrect.
✅ Correct Logic Should Be:
Keep the character only if it’s not equal to the previous character.
✔️ Cleaned Up Version of the Algorithm:
python
s = "afafasgggewrtdg"
t = ""
last_seen_character = Nonefor c in s:
if c != last_seen_character:
t += c
last_seen_character = c
print(t)
🧪 Example:
Input:"aabaaabb" Output:"abab"
⏱️ Time Complexity: O(n)
You visit each character once.
📦 Space Complexity: O(n)
In the worst case, the output string could be the same length as input.
🧠 Final Thoughts:
You're on the right track with tracking characters, but overcomplicating it with multiple conditions and flags. Stick to comparing only the current and previous characters — that’s sufficient here.
Let me know if you want to walk through more test cases or edge conditions!
So The Solution Is:
s = "afafasgggewrtdg"
t = ""
last_seen_character = None
for c in s:
if c != last_seen_character:
t += c
last_seen_character = c
print(t)
