Module Week 4

Reverse Vowels of a String

LeetCode 345

Easy ▼

Source

LeetCode 345 - Reverse Vowels of a String

Problem

Given a string s, reverse only all the vowels in the string and return it. The vowels are a, e, i, o, and u, and they can appear in both lower and upper cases, more than once.

Function Signature

reverseVowels(s: string) -> string

Examples

Input: s = "hello"
Output: "holle"

Input: s = "leetcode"
Output: "leotcede"

The key phrase: "reverse only all the vowels". Consonants don't move. Only the vowels swap positions with each other.

For "hello" the vowels are e (index 1) and o (index 4). Swap them to get "holle". The h, l, l stay put.

Also note: vowels can be upper or lower case. Handle both a and A.

We need to pair up vowels from opposite ends and swap them. First vowel from the left swaps with the first from the right, and so on inward.

Use two pointers, one at the start, one at the end. Each skips consonants and stops on a vowel. When both land on vowels, swap and move inward.

Store all 10 vowel characters in a set so each "is this a vowel?" check is instant.

⚙ Knowledge Hub: Using Sets

In many languages strings are immutable, so work with a mutable copy (e.g. a char array) so you can swap in place
Put all 10 vowels (aeiouAEIOU) in a set so you can check membership instantly
Start two pointers: left = 0, right = length - 1
Use inner while loops to advance left forward and right backward, skipping anything that isn't a vowel. Always guard with left < right
Once both pointers sit on vowels, swap those two characters, then nudge both pointers inward (left++, right--)
The outer loop ends when the pointers meet or cross. Return the modified result

def reverseVowels(s):
    vowels = set("aeiouAEIOU")
    s = list(s)  # mutable copy
    l, r = 0, len(s) - 1
    while l < r:
        while l < r and s[l] not in vowels: l += 1  # skip consonants
        while l < r and s[r] not in vowels: r -= 1
        s[l], s[r] = s[r], s[l]  # swap vowels
        l += 1; r -= 1
    return "".join(s)

string reverseVowels(string s) {
    unordered_set<char> v("aeiouAEIOU",
                            "aeiouAEIOU" + 10);  // vowel set
    int l = 0, r = s.size() - 1;
    while (l < r) {
        while (l < r && !v.count(s[l])) l++;  // skip consonants
        while (l < r && !v.count(s[r])) r--;
        swap(s[l++], s[r--]);  // swap vowels
    }
    return s;
}

public string ReverseVowels(string s) {
    var v = new HashSet<char>("aeiouAEIOU");
    char[] a = s.ToCharArray();  // mutable copy
    int l = 0, r = a.Length - 1;
    while (l < r) {
        while (l < r && !v.Contains(a[l])) l++;  // skip consonants
        while (l < r && !v.Contains(a[r])) r--;
        (a[l], a[r]) = (a[r], a[l]);  // swap vowels
        l++; r--;
    }
    return new string(a);
}

public String reverseVowels(String s) {
    Set<Character> v = new HashSet<>(
        Arrays.asList('a','e','i','o','u','A','E','I','O','U'));
    char[] a = s.toCharArray();  // mutable copy
    int l = 0, r = a.length - 1;
    while (l < r) {
        while (l < r && !v.contains(a[l])) l++;  // skip consonants
        while (l < r && !v.contains(a[r])) r--;
        char t = a[l]; a[l] = a[r]; a[r] = t;  // swap vowels
        l++; r--;
    }
    return new String(a);
}

A stack is last-in-first-out. If you push all the vowels onto a stack in left-to-right order, popping them gives you the vowels in reverse order, which is exactly what we need.

This is a different way to think about the same problem. Instead of swapping in place with two pointers, we collect, reverse via the stack, then place them back.

⚙ Knowledge Hub: Using Stacks

Put all 10 vowels (aeiouAEIOU) in a set for instant membership checks
Pass 1 (collect): Loop through the string left to right. Every time the current character is in your vowel set, push it onto a stack
Pass 2 (rebuild): Loop through the string again. For each character: if it's a vowel, pop from the stack and use that instead; otherwise keep the original character. Build the result as you go.
Because the stack is LIFO, the last vowel collected is the first one placed, so this naturally reverses the vowel order
Return the rebuilt string

def reverseVowels(s):
    vowels = set("aeiouAEIOU")
    stack = [c for c in s if c in vowels]  # collect vowels
    result = []
    for c in s:
        if c in vowels:
            result.append(stack.pop())  # pop gives reverse order
        else:
            result.append(c)
    return "".join(result)

string reverseVowels(string s) {
    unordered_set<char> v("aeiouAEIOU",
                            "aeiouAEIOU" + 10);  // vowel set
    vector<char> st;  // use vector as stack
    for (char c : s)  // pass 1: collect vowels
        if (v.count(c)) st.push_back(c);
    string res;
    for (char c : s) {  // pass 2: rebuild with reversed vowels
        if (v.count(c)) {
            res += st.back(); st.pop_back();
        } else {
            res += c;
        }
    }
    return res;
}

public string ReverseVowels(string s) {
    var v = new HashSet<char>("aeiouAEIOU");
    var st = new Stack<char>();
    foreach (char c in s)  // pass 1: collect vowels
        if (v.Contains(c)) st.Push(c);
    var sb = new StringBuilder();
    foreach (char c in s)  // pass 2: pop reverses order
        sb.Append(v.Contains(c) ? st.Pop() : c);
    return sb.ToString();
}

public String reverseVowels(String s) {
    Set<Character> v = new HashSet<>(
        Arrays.asList('a','e','i','o','u','A','E','I','O','U'));
    Stack<Character> st = new Stack<>();
    for (char c : s.toCharArray())  // pass 1: collect vowels
        if (v.contains(c)) st.push(c);
    StringBuilder sb = new StringBuilder();
    for (char c : s.toCharArray())  // pass 2: pop reverses order
        sb.append(v.contains(c) ? st.pop() : c);
    return sb.toString();
}

Isomorphic Strings

LeetCode 205

Easy ▼

Source

LeetCode 205 - Isomorphic Strings

Problem

Given two strings s and t, determine if they are isomorphic. Two strings are isomorphic if the characters in s can be replaced to get t. All occurrences of a character must be replaced with another character while preserving the order. No two characters may map to the same character, but a character may map to itself.

Function Signature

isIsomorphic(s: string, t: string) -> boolean

Examples

Input: s = "egg", t = "add"
Output: True

Input: s = "foo", t = "bar"
Output: False

Input: s = "paper", t = "title"
Output: True

Key phrase: "characters in s can be replaced to get t". Every character in s must consistently map to the same character in t. For "egg" to "add": e always maps to a, g always maps to d.

Critical detail: "no two characters may map to the same character". It's a one-to-one relationship. If e->a, nothing else can map to a.

We need to track which character maps to which. Use a dictionary to store the mapping and check it on each new pair.

⚙ Knowledge Hub: Using Dictionaries

One map (s->t) alone misses cases. Try s = "badc", t = "baba". A forward map accepts it, but both b and d map to b. That violates the one-to-one rule.

Add a reverse map (t->s). Now every mapping is checked in both directions.

Create two empty dictionaries, one for the forward mapping (s->t) and one for the reverse (t->s)
Loop through both strings at the same index. At each position you're looking at a character from s and the character at the same position in t
For each pair: check if you've already recorded a mapping for either character. If you have, make sure it's consistent. The s character must still map to the same t character as before, and vice versa. Any mismatch means the strings aren't isomorphic, so return false
If neither character has been seen yet, record the mapping in both dictionaries and continue
If you reach the end without a conflict, return true

def isIsomorphic(s, t):
    map_s, map_t = {}, {}  # forward and reverse maps
    for c1, c2 in zip(s, t):
        if c1 in map_s and map_s[c1] != c2: return False  # conflict
        if c2 in map_t and map_t[c2] != c1: return False
        map_s[c1] = c2
        map_t[c2] = c1
    return True

bool isIsomorphic(string s, string t) {
    unordered_map<char,char> ms, mt;  // forward and reverse maps
    for (int i = 0; i < s.size(); i++) {
        if (ms.count(s[i]) && ms[s[i]] != t[i]) return false;  // conflict
        if (mt.count(t[i]) && mt[t[i]] != s[i]) return false;
        ms[s[i]] = t[i];
        mt[t[i]] = s[i];
    }
    return true;
}

public bool IsIsomorphic(string s, string t) {
    var ms = new Dictionary<char,char>();  // forward and reverse maps
    var mt = new Dictionary<char,char>();
    for (int i = 0; i < s.Length; i++) {
        if (ms.ContainsKey(s[i]) && ms[s[i]] != t[i]) return false;  // conflict
        if (mt.ContainsKey(t[i]) && mt[t[i]] != s[i]) return false;
        ms[s[i]] = t[i];
        mt[t[i]] = s[i];
    }
    return true;
}

public boolean isIsomorphic(String s, String t) {
    Map<Character,Character> ms = new HashMap<>();  // forward and reverse maps
    Map<Character,Character> mt = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        char a = s.charAt(i), b = t.charAt(i);
        if (ms.containsKey(a) && ms.get(a) != b) return false;  // conflict
        if (mt.containsKey(b) && mt.get(b) != a) return false;
        ms.put(a, b);
        mt.put(b, a);
    }
    return true;
}

The Grid Search

HackerRank

Medium ▼

Source

HackerRank - The Grid Search

Problem

Given a 2D array of digits (the grid) and a smaller 2D pattern of digits, determine whether the pattern exists anywhere within the grid. Each row is represented as a string of digits.

Function Signature

gridSearch(G: string[], P: string[]) -> "YES" | "NO"

Example

Grid (7 rows):
"7283455864"
"6731158619"
"8988242643"
"3830589324"
"2229505813"
"5633845374"
"6473530293"

Pattern (3 rows):
"9505"
"3845"
"3530"

Output: "YES"

We have a big grid of digit strings and a smaller pattern. The question: does this smaller block appear anywhere inside the larger one?

The pattern has multiple rows, so you need to find a position where every row of the pattern matches the corresponding section of the grid at the same time.

The pattern can only start where there's room for it to fit. If the grid has R rows and the pattern has r rows, valid starting rows are 0 through R - r. Same for columns.

Always calculate valid bounds first. This prevents off-by-one errors.

Read off the dimensions you'll need: rg, cg (grid rows/cols) and rp, cp (pattern rows/cols)
The pattern can only start at row i if i + rp <= rg, and column j if j + cp <= cg. Use two nested loops over these valid ranges
For each candidate position (i, j), run a third loop k = 0..rp-1 comparing one pattern row at a time: extract a substring of length cp from G[i+k] starting at column j, and check if it equals P[k]
If any row doesn't match, set a flag (found = false) and break out early since there's no need to check the rest
If all rp rows matched, you've found the pattern, so return "YES"
If you exhaust every position without a full match, return "NO"

def gridSearch(G, P):
    rg, rp = len(G), len(P)
    cg, cp = len(G[0]), len(P[0])

    for i in range(rg - rp + 1):  # valid starting rows
        for j in range(cg - cp + 1):  # valid starting cols
            found = True
            for k in range(rp):  # check each pattern row
                if G[i + k][j:j + cp] != P[k]:
                    found = False
                    break
            if found:
                return "YES"
    return "NO"

string gridSearch(vector<string> G, vector<string> P) {
    int rg = G.size(), rp = P.size();
    int cg = G[0].size(), cp = P[0].size();
    for (int i = 0; i <= rg-rp; i++)  // try each top-left corner
        for (int j = 0; j <= cg-cp; j++) {
            bool ok = true;
            for (int k = 0; k < rp && ok; k++)  // match each row
                if (G[i+k].substr(j,cp) != P[k]) ok = false;
            if (ok) return "YES";
        }
    return "NO";
}

public string GridSearch(string[] G, string[] P) {
    int rg = G.Length, rp = P.Length;
    int cg = G[0].Length, cp = P[0].Length;
    for (int i = 0; i <= rg-rp; i++)  // try each top-left corner
        for (int j = 0; j <= cg-cp; j++) {
            bool ok = true;
            for (int k = 0; k < rp && ok; k++)  // match each row
                if (G[i+k].Substring(j,cp) != P[k]) ok = false;
            if (ok) return "YES";
        }
    return "NO";
}

public String gridSearch(String[] G, String[] P) {
    int rg = G.length, rp = P.length;
    int cg = G[0].length(), cp = P[0].length();
    for (int i = 0; i <= rg-rp; i++)  // try each top-left corner
        for (int j = 0; j <= cg-cp; j++) {
            boolean ok = true;
            for (int k = 0; k < rp && ok; k++)  // match each row
                if (!G[i+k].substring(j,j+cp).equals(P[k])) ok = false;
            if (ok) return "YES";
        }
    return "NO";
}

Queen's Attack II

HackerRank

Hard ▼

Source

HackerRank - Queen's Attack II

Problem

A queen is standing on an n×n chessboard. She can attack any square in the same row, column, or diagonal, but obstacles block her path. Calculate the number of squares the queen can attack.

Parameters

n - board size (n×n)
k - number of obstacles
r_q, c_q - queen's position (1-indexed)
obstacles - list of [row, col] positions

Example

n = 5, k = 3, queen at (4, 3)
obstacles = [[5,5], [4,2], [2,3]]
Output: 10

The queen attacks in 8 directions: up, down, left, right, and four diagonals. She moves any number of squares until she hits the board edge or an obstacle.

Obstacles block her. She stops before the obstacle, not on it. Count every valid square she can reach across all 8 directions.

For each step the queen takes, we need to check: "is there an obstacle here?" Scanning the obstacle list every time is too slow for large boards.

Put all obstacle positions in a set. Each lookup becomes instant. Sets use the same hash-based approach as dictionaries, just keys without values.

⚙ Knowledge Hub: Using Sets

Loop through the obstacle list and add each (row, col) to a set. This gives you O(1) "is there an obstacle here?" checks later
Define the 8 directions as an array of offset pairs: (-1,0) up, (1,0) down, (0,1) right, (0,-1) left, and the four diagonals (-1,1), (-1,-1), (1,1), (1,-1)
For each direction (dr, dc): start at the queen's position and use a while true loop, adding dr/dc each step to move outward
On each step, check two things in order: (1) is the new position off the board? (r < 1 or r > n or same for c). If so, break. (2) is it in the obstacle set? If so, break. Otherwise increment a counter.
After all 8 directions are done, the counter holds the total number of attackable squares. Return it

def queensAttack(n, k, r_q, c_q, obstacles):
    obs = set()
    for o in obstacles:
        obs.add((o[0], o[1]))  # set for fast lookup

    dirs = [(-1,0),(1,0),(0,1),(0,-1),
            (-1,1),(-1,-1),(1,1),(1,-1)]  # 8 directions

    total = 0
    for dr, dc in dirs:
        r, c = r_q, c_q
        while True:
            r += dr; c += dc
            if r < 1 or r > n or c < 1 or c > n: break  # off board
            if (r, c) in obs: break  # blocked
            total += 1
    return total

int queensAttack(int n, int k, int rq, int cq,
                 vector<vector<int>> obs_list) {
    set<pair<int,int>> obs;
    for (auto& o : obs_list)
        obs.insert({o[0], o[1]});  // set for fast lookup
    int dirs[][2] = {{-1,0},{1,0},{0,1},{0,-1},
                      {-1,1},{-1,-1},{1,1},{1,-1}};  // 8 directions
    int total = 0;
    for (auto& d : dirs) {
        int r = rq, c = cq;
        while (true) {
            r += d[0]; c += d[1];
            if (r<1||r>n||c<1||c>n) break;  // off board
            if (obs.count({r,c})) break;  // blocked
            total++;
        }
    }
    return total;
}

public int QueensAttack(int n, int k, int rq, int cq,
                       int[][] obsList) {
    var obs = new HashSet<(int,int)>();
    foreach (var o in obsList)
        obs.Add((o[0], o[1]));  // set for fast lookup
    int[][] dirs = {
        new[]{-1,0},new[]{1,0},new[]{0,1},new[]{0,-1},
        new[]{-1,1},new[]{-1,-1},new[]{1,1},new[]{1,-1}};  // 8 directions
    int total = 0;
    foreach (var d in dirs) {
        int r = rq, c = cq;
        while (true) {
            r += d[0]; c += d[1];
            if (r<1||r>n||c<1||c>n) break;  // off board
            if (obs.Contains((r,c))) break;  // blocked
            total++;
        }
    }
    return total;
}

public int queensAttack(int n, int k, int rq, int cq,
                        int[][] obsList) {
    Set<String> obs = new HashSet<>();
    for (int[] o : obsList)
        obs.add(o[0]+","+o[1]);  // set for fast lookup
    int[][] dirs = {{-1,0},{1,0},{0,1},{0,-1},
                     {-1,1},{-1,-1},{1,1},{1,-1}};  // 8 directions
    int total = 0;
    for (int[] d : dirs) {
        int r = rq, c = cq;
        while (true) {
            r += d[0]; c += d[1];
            if (r<1||r>n||c<1||c>n) break;  // off board
            if (obs.contains(r+","+c)) break;  // blocked
            total++;
        }
    }
    return total;
}

MODULE WEEK 4