🚀 Finding the Length of the Longest Substring Without Repeating Characters

When preparing for interviews or working with string algorithms, one classic problem is:

Given a string s, return the length of the longest substring without repeating characters.

Example:

• Input: "abcabcbb"

• Output: 3 (because "abc" is the longest substring without repeating chars)

---

🧩 Problem Intuition

We want the longest contiguous substring where no character repeats.
Naively, we could try every substring (O(n²)) and check uniqueness, but that’s too slow for larger inputs.

Instead, we use a sliding window:

• Expand the right boundary to include characters.

• If a duplicate appears, shrink the left boundary until the window is valid again.

• Track the maximum length as we go.

---

🛠️ Sliding Window + Hashing Approach

Core Ideas:

1. Maintain two pointers: l (left) and r (right).

2. Keep a map of last-seen indices of each character.

3. For each character at r:

   • If it’s already in the current window (map[ch] >= l), move l to map[ch] + 1.

   • Update the last-seen index of ch.

   • Update the max length.

This ensures each character is processed at most twice (once when r expands, once when l moves), giving us O(n) time.

---

💻 Java Implementation

import java.util.Arrays;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int l = 0, r = 0;
        int[] map = new int[256]; // supports ASCII
        Arrays.fill(map, -1);

        int maxLen = 0;
        while (r < s.length()) {
            char ch = s.charAt(r);

            // if char seen in current window, move left pointer
            if (map[ch] >= l) {
                l = map[ch] + 1;
            }

            // update window
            map[ch] = r;
            maxLen = Math.max(maxLen, r - l + 1);

            r++;
        }
        return maxLen;
    }
}

---

📊 Complexity Analysis

• Time Complexity: O(n) → each character visited at most twice.

• Space Complexity: O(1) → fixed-size array (256) for ASCII.
  For Unicode, switch to HashMap<Character,Integer>.

---

🔑 Key Takeaways

• Sliding window problems often involve two pointers and a hash structure.

• Always update your left pointer only when duplicates fall inside the current window.

• This problem demonstrates the balance between correctness and efficiency — no need to brute force!

---

✅ Next step: try extending this logic to variations like:

• Longest substring with at most k distinct characters

• Longest substring where characters can repeat up to m times

Google code jam :Minimum Scalar Product

Problem

You are given two vectors v1=(x1,x2,...,xn) and v2=(y1,y2,...,yn). The scalar product of these vectors is a single number, calculated as x1y1+x2y2+...+xnyn.

Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum scalar product.

Google Code jam:Reverse Words in O(nm)

Problem

Given a list of space separated words, reverse the order of the words. Each line of text contains L letters and W words. A line will only consist of letters and space characters. There will be exactly one space character between each pair of consecutive words.