Module Week 7

Ransom Note

LeetCode 383

Easy ▼

Source

LeetCode 383 - Ransom Note

Problem

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise. Each letter in magazine can only be used once in ransomNote.

Function Signature

canConstruct(ransomNote: string, magazine: string) -> bool

Examples

Input: ransomNote = "a", magazine = "b"
Output: false

Input: ransomNote = "aa", magazine = "ab"
Output: false

Input: ransomNote = "aa", magazine = "aab"
Output: true

This is a problem which has a lot in common with others we have solved in earlier weeks. The core task is one you should have solved before.

You need to check whether the magazine contains enough of each letter to build the ransom note. Each letter in the magazine can only be used once.

This is a frequency counting problem. Count how many times each letter appears in the magazine. Then check that every letter the ransom note needs is available in sufficient quantity.

⚙ Knowledge Hub: Counting Frequencies

Build a frequency map of the magazine's letters
Loop through each letter in the ransom note
For each letter, check the map. If the count is zero or the letter is missing, return false
Otherwise, decrement that letter's count and continue
If you get through the entire ransom note without running out, return true

This is the same pattern as checking whether one string is an anagram of another. The only difference is that the magazine is allowed to have leftover letters.

from collections import Counter

def canConstruct(ransomNote, magazine):
    freq = Counter(magazine)
    for ch in ransomNote:
        if freq[ch] <= 0:
            return False
        freq[ch] -= 1
    return True

bool canConstruct(string ransomNote, string magazine) {
    int freq[26] = {};
    for (char c : magazine) freq[c - 'a']++;
    for (char c : ransomNote) {
        if (--freq[c - 'a'] < 0) return false;
    }
    return true;
}

public bool CanConstruct(string ransomNote, string magazine) {
    int[] freq = new int[26];
    foreach (char c in magazine) freq[c - 'a']++;
    foreach (char c in ransomNote) {
        if (--freq[c - 'a'] < 0) return false;
    }
    return true;
}

public boolean canConstruct(String ransomNote, String magazine) {
    int[] freq = new int[26];
    for (char c : magazine.toCharArray()) freq[c - 'a']++;
    for (char c : ransomNote.toCharArray()) {
        if (--freq[c - 'a'] < 0) return false;
    }
    return true;
}

Modified Kaprekar Numbers

HackerRank

Easy ▼

Source

HackerRank - Modified Kaprekar Numbers

Problem

A modified Kaprekar number is a positive whole number with a special property. If you square it, then split the string representation of the square into two parts and sum those parts, you get the original number. The right-hand part must have the same number of digits as the original number. The left part is whatever remains. Given two positive integers p and q, find and print the modified Kaprekar numbers in the range between p and q, inclusive. If none exist in the range, print INVALID RANGE.

Function Signature

kaprekarNumbers(p: int, q: int) -> void (prints result)

Examples

Input: p = 1, q = 100
Output: 1 9 45 55 99
Explanation: For example, 45² = 2025. Split into "20" and "25": 20 + 25 = 45.

Input: p = 400, q = 700
Output: INVALID RANGE

This one is straightforward but fiddly. You need to read the description very carefully. Earlier problems on manipulating digits of integers, and string manipulation in general, are relevant here.

The key detail is how you split the squared number: the right part must have the same number of digits as the original number. The left part is whatever is left over (and may be empty, in which case treat it as 0).

This is a string manipulation problem. For each number in the range, square it, convert the result to a string, then split it at the correct position. Convert both halves back to integers and check whether they sum to the original number.

Loop through every number n from p to q
Compute sq = n * n and convert it to a string
Find d, the number of digits in n
Split the string of sq so that the right part has exactly d digits. The left part is everything before that
Convert both parts to integers (treat an empty left part as 0)
If left + right == n, it is a modified Kaprekar number
Collect all results and print them space-separated, or print INVALID RANGE if none were found

Watch out for the number 1: 1² = 1, which splits into "" and "1". The empty left part is 0, and 0 + 1 = 1, so 1 is a valid Kaprekar number.

def kaprekarNumbers(p, q):
    results = []
    for n in range(p, q + 1):
        sq = str(n * n)
        d = len(str(n))
        right = int(sq[-d:])
        left = int(sq[:-d]) if len(sq) > d else 0
        if left + right == n:
            results.append(str(n))
    if results:
        print(" ".join(results))
    else:
        print("INVALID RANGE")

void kaprekarNumbers(int p, int q) {
    vector<int> results;
    for (int n = p; n <= q; n++) {
        long long sq = (long long)n * n;
        string s = to_string(sq);
        int d = to_string(n).size();
        long long right = stoll(s.substr(s.size() - d));
        long long left = s.size() > d ? stoll(s.substr(0, s.size() - d)) : 0;
        if (left + right == n)
            results.push_back(n);
    }
    if (results.empty()) cout << "INVALID RANGE";
    else for (int i = 0; i < results.size(); i++)
        cout << (i ? " " : "") << results[i];
    cout << endl;
}

public static void kaprekarNumbers(int p, int q) {
    var results = new List<int>();
    for (int n = p; n <= q; n++) {
        long sq = (long)n * n;
        string s = sq.ToString();
        int d = n.ToString().Length;
        long right = long.Parse(s.Substring(s.Length - d));
        long left = s.Length > d ? long.Parse(s.Substring(0, s.Length - d)) : 0;
        if (left + right == n)
            results.Add(n);
    }
    if (results.Count == 0)
        Console.WriteLine("INVALID RANGE");
    else
        Console.WriteLine(string.Join(" ", results));
}

static void kaprekarNumbers(int p, int q) {
    List<Integer> results = new ArrayList<>();
    for (int n = p; n <= q; n++) {
        long sq = (long) n * n;
        String s = Long.toString(sq);
        int d = String.valueOf(n).length();
        long right = Long.parseLong(s.substring(s.length() - d));
        long left = s.length() > d ? Long.parseLong(s.substring(0, s.length() - d)) : 0;
        if (left + right == n)
            results.add(n);
    }
    if (results.isEmpty())
        System.out.println("INVALID RANGE");
    else {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < results.size(); i++) {
            if (i > 0) sb.append(" ");
            sb.append(results.get(i));
        }
        System.out.println(sb);
    }
}

Maximum Product of Word Lengths

LeetCode 318

Medium ▼

Source

LeetCode 318 - Maximum Product of Word Lengths

Problem

Given a string array words, return the maximum value of length(words[i]) * length(words[j]) where the two words do not share common letters. If no such two words exist, return 0.

Function Signature

maxProduct(words: string[]) -> int

Examples

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words are "abcw" and "xtfn".

Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words are "ab" and "cd".

Input: words = ["a","aa","aaa","aaaa"]
Output: 0
Explanation: Every pair shares the letter 'a'.

For this one, think about how to quickly test whether two words have letters in common. Preprocessing helps speed this up.

You need to check every pair of words and find the pair with the largest product of lengths, but only if they share no letters at all.

Use bit manipulation to represent each word as a bitmask. There are only 26 lowercase letters, so each word's letter set fits in a single integer. Set bit i if the word contains the i-th letter of the alphabet.

Two words share no letters if and only if their bitmasks ANDed together equal zero.

⚙ Knowledge Hub: Bit Masking

Preprocess: for each word, build a 26-bit integer where bit i is set if the word contains that letter. Use mask |= 1 << (ch - 'a')
Compare every pair of words (i, j)
If masks[i] & masks[j] == 0, the words share no letters
Track the maximum product of len(words[i]) * len(words[j])

The bitmask approach reduces the "do these words share a letter?" check from a loop over characters to a single bitwise AND operation.

def maxProduct(words):
    masks = []
    for w in words:
        mask = 0
        for ch in w:
            mask |= 1 << (ord(ch) - ord('a'))
        masks.append(mask)

    best = 0
    for i in range(len(words)):
        for j in range(i + 1, len(words)):
            if masks[i] & masks[j] == 0:
                best = max(best, len(words[i]) * len(words[j]))
    return best

int maxProduct(vector<string>& words) {
    int n = words.size();
    vector<int> masks(n, 0);
    for (int i = 0; i < n; i++)
        for (char c : words[i])
            masks[i] |= 1 << (c - 'a');
    int best = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if ((masks[i] & masks[j]) == 0)
                best = max(best, (int)(words[i].size() * words[j].size()));
    return best;
}

public int MaxProduct(string[] words) {
    int n = words.Length;
    int[] masks = new int[n];
    for (int i = 0; i < n; i++)
        foreach (char c in words[i])
            masks[i] |= 1 << (c - 'a');
    int best = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if ((masks[i] & masks[j]) == 0)
                best = Math.Max(best, words[i].Length * words[j].Length);
    return best;
}

public int maxProduct(String[] words) {
    int n = words.length;
    int[] masks = new int[n];
    for (int i = 0; i < n; i++)
        for (char c : words[i].toCharArray())
            masks[i] |= 1 << (c - 'a');
    int best = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if ((masks[i] & masks[j]) == 0)
                best = Math.max(best, words[i].length() * words[j].length());
    return best;
}

Gridland Metro

HackerRank

Medium ▼

Source

HackerRank - Gridland Metro

Problem

The city of Gridland is represented as an n × m grid where rows are numbered 1 to n and columns 1 to m. There is a network of train tracks that run in straight horizontal lines along a row, from column c1 to column c2. Tracks on the same row may overlap. The mayor wants to place lampposts in cells not occupied by any track. Given the grid dimensions and the list of tracks, find the number of cells where lampposts can be placed.

Function Signature

gridlandMetro(n: int, m: int, k: int, track: int[][]) -> long

Examples

Input: n = 4, m = 4, k = 3, track = [[2,2,3],[3,1,4],[4,4,4]]
Output: 9
Explanation: Row 1 is entirely free (4 cells). Row 2 has columns 2-3 occupied (2 free). Row 3 is fully occupied (0 free). Row 4 has column 4 occupied (3 free). Total = 4 + 2 + 0 + 3 = 9.

This is a tough medium with an underlying theme of 2D spatial grids. The size can get very large (up to a billion cells in each direction), so you need to find a way of doing this without actually storing the grid.

Tracks on the same row can overlap, so you need to merge overlapping intervals before counting occupied cells.

This is an interval merging problem. Group tracks by row. For each row that has tracks, sort the intervals by start column and merge any that overlap. The total occupied cells in that row is the sum of merged interval lengths. Subtract from m to get free cells for that row.

Rows with no tracks are entirely free (m cells each). You will also need to use 64-bit integers in languages without big integers, since n * m can exceed 2³¹.

Start with total free cells = n * m (using 64-bit arithmetic)
Group all tracks by row number using a dictionary
For each row that has tracks, sort the intervals by c1
Merge overlapping intervals: walk through the sorted list, extending the current interval when there is overlap, and starting a new interval when there is a gap
Sum the lengths of the merged intervals. That is the number of occupied cells in this row. Subtract it from the total
Return the remaining total

You only need to process rows that actually contain tracks. Every other row contributes a full m free cells, which is already accounted for in the initial n * m.

from collections import defaultdict

def gridlandMetro(n, m, k, track):
    rows = defaultdict(list)
    for r, c1, c2 in track:
        rows[r].append((c1, c2))

    occupied = 0
    for r in rows:
        intervals = sorted(rows[r])
        merged_start, merged_end = intervals[0]
        for c1, c2 in intervals[1:]:
            if c1 <= merged_end + 1:
                merged_end = max(merged_end, c2)
            else:
                occupied += merged_end - merged_start + 1
                merged_start, merged_end = c1, c2
        occupied += merged_end - merged_start + 1

    return n * m - occupied

long long gridlandMetro(int n, int m, int k,
        vector<vector<int>>& track) {
    unordered_map<int, vector<pair<int,int>>> rows;
    for (auto& t : track)
        rows[t[0]].push_back({t[1], t[2]});
    long long occupied = 0;
    for (auto& [r, segs] : rows) {
        sort(segs.begin(), segs.end());
        int ms = segs[0].first, me = segs[0].second;
        for (int i = 1; i < segs.size(); i++) {
            if (segs[i].first <= me + 1)
                me = max(me, segs[i].second);
            else {
                occupied += me - ms + 1;
                ms = segs[i].first; me = segs[i].second;
            }
        }
        occupied += me - ms + 1;
    }
    return (long long)n * m - occupied;
}

public static long gridlandMetro(int n, int m, int k,
        int[][] track) {
    var rows = new Dictionary<int, List<(int, int)>>();
    foreach (var t in track) {
        if (!rows.ContainsKey(t[0]))
            rows[t[0]] = new List<(int, int)>();
        rows[t[0]].Add((t[1], t[2]));
    }
    long occupied = 0;
    foreach (var kv in rows) {
        var segs = kv.Value;
        segs.Sort();
        int ms = segs[0].Item1, me = segs[0].Item2;
        for (int i = 1; i < segs.Count; i++) {
            if (segs[i].Item1 <= me + 1)
                me = Math.Max(me, segs[i].Item2);
            else {
                occupied += me - ms + 1;
                ms = segs[i].Item1; me = segs[i].Item2;
            }
        }
        occupied += me - ms + 1;
    }
    return (long)n * m - occupied;
}

public static long gridlandMetro(int n, int m, int k,
        int[][] track) {
    Map<Integer, List<int[]>> rows = new HashMap<>();
    for (int[] t : track)
        rows.computeIfAbsent(t[0], x -> new ArrayList<>())
             .add(new int[]{t[1], t[2]});
    long occupied = 0;
    for (List<int[]> segs : rows.values()) {
        segs.sort((a, b) -> a[0] - b[0]);
        int ms = segs.get(0)[0], me = segs.get(0)[1];
        for (int i = 1; i < segs.size(); i++) {
            if (segs.get(i)[0] <= me + 1)
                me = Math.max(me, segs.get(i)[1]);
            else {
                occupied += me - ms + 1;
                ms = segs.get(i)[0];
                me = segs.get(i)[1];
            }
        }
        occupied += me - ms + 1;
    }
    return (long) n * m - occupied;
}

MODULE WEEK 7