Sandwiched_Vowels

Summary

The problem "Sandwiched Vowels" involves a given string and its vowels. The task is to find all the substrings that have at least one vowel, but no other vowels in between. This means that if there are any vowels in the substring, they should be sandwiched by non-vowel characters.

Detailed Explanation

The problem can be approached by iterating over the input string and checking each character for being a vowel or not. If a character is a vowel, we store it as part of our current substring. As soon as we find a non-vowel character, we check if our current substring has at least one vowel. If it does, we add this substring to our result list.

Here's the step-by-step breakdown:

• Initialize an empty list result to store all valid substrings.
• Iterate over each character in the input string.
• Check if the character is a vowel (either 'a', 'e', 'i', 'o', or 'u'). If it is:
  • Store this character as part of our current substring.
• If the character is not a vowel:
  • Check if our current substring has at least one vowel. If it does, add this substring to result.
  • Reset our current substring to an empty string.
• After iterating over all characters in the input string, return the result list.

Time complexity: O(n), where n is the length of the input string. We only iterate over the string once. Space complexity: O(n), as we store at most n substrings (if every character is a vowel).

Optimized Solutions

Java

java
import java.util.ArrayList;
import java.util.List;

public List<String> sandwichedVowels(String s) {
    List<String> result = new ArrayList<>();
    StringBuilder currentSubstring = new StringBuilder();

    for (char c : s.toCharArray()) {
        if (isVowel(c)) {
            currentSubstring.append(c);
        } else {
            if (currentSubstring.length() > 0 && hasVowel(currentSubstring.toString())) {
                result.add(currentSubstring.toString());
            }
            currentSubstring.setLength(0);
        }
    }

    if (hasVowel(currentSubstring.toString())) {
        result.add(currentSubstring.toString());
    }

    return result;
}

private boolean isVowel(char c) {
    String vowels = "aeiouAEIOU";
    return vowels.indexOf(c) != -1;
}

private boolean hasVowel(String s) {
    for (char c : s.toCharArray()) {
        if (isVowel(c)) {
            return true;
        }
    }
    return false;
}

Python

python
def sandwiched_vowels(s):
    result = []
    current_substring = ""

    for char in s:
        if is_vowel(char):
            current_substring += char
        else:
            if current_substring and has_vowel(current_substring):
                result.append(current_substring)
            current_substring = ""

    if current_substring and has_vowel(current_substring):
        result.append(current_substring)

    return result

def is_vowel(char):
    vowels = "aeiouAEIOU"
    return char in vowels

def has_vowel(s):
    for char in s:
        if is_vowel(char):
            return True
    return False

C++

cpp
#include <vector>
#include <string>

std::vector<std::string> sandwichedVowels(const std::string& s) {
    std::vector<std::string> result;
    std::string currentSubstring;

    for (char c : s) {
        if (isVowel(c)) {
            currentSubstring += c;
        } else {
            if (!currentSubstring.empty() && hasVowel(currentSubstring)) {
                result.push_back(currentSubstring);
            }
            currentSubstring.clear();
        }
    }

    if (!currentSubstring.empty() && hasVowel(currentSubstring)) {
        result.push_back(currentSubstring);
    }

    return result;
}

bool isVowel(char c) {
    std::string vowels = "aeiouAEIOU";
    return std::find(vowels.begin(), vowels.end(), c) != vowels.end();
}

bool hasVowel(const std::string& s) {
    for (char c : s) {
        if (isVowel(c)) {
            return true;
        }
    }
    return false;
}

JavaScript

javascript
function sandwichedVowels(s) {
    const result = [];
    let currentSubstring = "";

    for (let char of s) {
        if (isVowel(char)) {
            currentSubstring += char;
        } else {
            if (currentSubstring && hasVowel(currentSubstring)) {
                result.push(currentSubstring);
            }
            currentSubstring = "";
        }
    }

    if (currentSubstring && hasVowel(currentSubstring)) {
        result.push(currentSubstring);
    }

    return result;
}

function isVowel(char) {
    const vowels = "aeiouAEIOU";
    return vowels.includes(char);
}

function hasVowel(s) {
    for (let char of s) {
        if (isVowel(char)) {
            return true;
        }
    }
    return false;
}