Discussion on "Longest Nice Substring" Problem

To See All Articles About Technology: Index of Lessons in Technology

Just The Problem Text

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

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

1. Iterate over all possible substrings of the given string s.

2. 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
def is_vowel(ch):
    return ch in 'aeiou'

def longest_nice_substring(s):
    n = len(s)
    max_len = 0

    for i in range(n):
        vowels = 0
        consonants = 0

        for j in range(i, n):
            if is_vowel(s[j]):
                vowels += 1
            else:
                consonants += 1

            if 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
def is_vowel(ch):
    return ch in 'aeiou'

def longest_nice_substring(s):
    n = len(s)
    prefix_sum = 0
    index_map = {0: -1}  # sum -> earliest index
    max_len = 0

    for i in range(n):
        if is_vowel(s[i]):
            prefix_sum += 1
        else:
            prefix_sum -= 1

        if 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.

---

🧱 Step-by-Step Explanation

Let's walk through this code:

1. Helper Function: To check for vowels

python
def is_vowel(ch):
    return ch in 'aeiou'

This simply checks if a character is a vowel.

---

2. Core Function Setup:

python
n = len(s)
prefix_sum = 0
index_map = {0: -1}
max_len = 0

• prefix_sum: This keeps a running total:

  • +1 for vowels

  • -1 for consonants

• index_map: Stores the first index at which each prefix sum value occurs.

  • Initially, we set 0: -1 to handle the case where the whole prefix from index 0 has a sum of 0.

• max_len: Stores the length of the longest "nice" substring found.

---

3. Iterate Through the String:

python
for i in range(n):
    if is_vowel(s[i]):
        prefix_sum += 1
    else:
        prefix_sum -= 1

As we go character by character, we update the prefix sum depending on whether we hit a vowel or consonant.

---

4. Check If Balance Seen Before:

python
    if prefix_sum in index_map:
        max_len = max(max_len, i - index_map[prefix_sum])
    else:
        index_map[prefix_sum] = i

• If we’ve seen this prefix sum before, that means:

  • The substring between that earlier index and the current one has a net sum of 0, i.e., equal vowels and consonants.

  • So we calculate i - earlier_index and update the max_len accordingly.

• If we haven’t seen this prefix sum before, we store the current index as the first occurrence.

---

👀 Example Walkthrough

Input:

ini
s = "aeiobcdfg"

Let's evaluate:

i	s[i]	Is Vowel?	prefix_sum	Seen Before?	Length if match	max_len
0	a	Yes	+1	No	-	0
1	e	Yes	+2	No	-	0
2	i	Yes	+3	No	-	0
3	o	Yes	+4	No	-	0
4	b	No	+3	Yes (@i=2)	4 - 2 = 2	2
5	c	No	+2	Yes (@i=1)	5 - 1 = 4	4
6	d	No	+1	Yes (@i=0)	6 - 0 = 6	6
7	f	No	0	Yes (@i=-1)	7 - (-1) = 8	8
8	g	No	-1	No	-	8

✅ Final answer: 8 (from index 0 to 7)

---

📊 Final Notes

• Time complexity: O(n) — you go through the string once.

• Space complexity: O(n) — for storing prefix sum indices in the hashmap.

---

Let me know if you'd like a visual diagram or if you want to handle upper-case letters, other alphabets, or build a full working test harness.