DEV Community: Gurpreet

Longest Substring Without Repeating Characters

Gurpreet — Fri, 24 Oct 2025 17:03:53 +0000

Given a string s, find the length of the longest substring without duplicate characters.

example 1

Input: s = "abcabcbb" Output: 3

Explanation: The answer is "abc", with the length of 3. Note that "bca" and "cab" are also correct answers.

Brute Force Approach:

Initialize a variable maxLength to 0.
Use a nested loop to generate every possible substring. The outer loop, with index i, defines the start of the substring. The inner loop, with index j, defines the end.
For each substring, use a third loop or a hash set to check if it contains repeating characters.
Create an empty set to store characters for the current substring.
Iterate through the substring from i to j.
For each character, check if it is already in the set. If it is, the substring has duplicates, so you can stop checking this substring.
If the character is not in the set, add it.
If the substring is found to have all unique characters, calculate its length (j - i + 1) and update maxLength if the new length is greater.
After checking all possible substrings, the final maxLength will be the answer.

Time Complexity: O(N³) The outer two loops that generate all substrings contribute O(N²).The inner check for unique characters in each substring takes an additional O(N) time in the worst case, leading to a total time complexity of O(N³). This can be optimized to O(N²) if the uniqueness check is done more efficiently by using a set that is cleared for each new substring.

Space Complexity: O(M). The space complexity is determined by the storage needed to check for unique characters in each substring. In the worst-case scenario, the substring could be the entire string, so a hash set would require space proportional to the number of unique characters, M, which is at most N.

Optimal Approach:

Sliding window technique with HashSet

Steps:

Initialize two pointers start and end at the beginning of the string and a HashSet set to store unique characters.
Iterate over the String using end.
If the character at end is not in hashset, insert character in hashset, calculate the current window size end-start+1 and increment end.
if the character is present in the hashset, shrink window from the left until the duplicate character is removed.
continue till end reaches end of the string.

Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len=0,start=0,end=0,n=s.length();
        HashSet set = new HashSet<>();

        while(end<n){
         while(set.contains(s.charAt(end))&& start<end){

            set.remove(s.charAt(start));
            start++;
         }
         set.add(s.charAt(end));
         len=Math.max(len,end-start+1);
         end++;
        }
        return len;



    }
}

Time Complexity

The time complexity of the sliding window approach using a hash set is O(N), where n is the length of the string.

The end pointer iterates through the string from start to end, processing each character once.

The start pointer also moves through the string, but it only advances forward. In the worst case, it will traverse the length of the string once.

The hash set operations—add, remove, and contains—have an average-case time complexity of O(1).

Since both pointers traverse the string linearly and the hash set operations are constant time, the overall time complexity is linear, or O(N).

Space Complexity

The space complexity is O(k) or O(min(N,k)), where k is the size of the character set (or alphabet).

The hash set stores unique characters within the current sliding window.

In the worst-case scenario, all characters in the string are unique, and the size of the hash set will be equal to the length of the string (N).

However, the size of the hash set is also bounded by the size of the character set. For example, with standard ASCII characters, the set can hold at most 128 elements.

Therefore, the space required is the minimum of the string length and the size of the character set. For a fixed, small character set like ASCII, the space complexity can be considered O(1)(constant).

The Magic Behind Instant Lookups: Understanding Hashing and Java's HashMap

Gurpreet — Wed, 22 Oct 2025 17:29:50 +0000

1. Hashing: The Core Concept

Hashing is a technique used to convert a large key into a small integer value that serves as an index in an array. This array is called a Hash Table. The primary goal is to achieve near-O(1) (constant time) complexity for insertion, deletion, and retrieval operations.

What is a Hash Function?
The Hash Function is the mathematical algorithm that performs the conversion. A good hash function is crucial for efficiency and should possess the following properties:

Deterministic: The same key must always produce the same hash code.
Uniform Distribution: It should distribute keys as evenly as possible across the entire range of hash table indices to minimize collisions.

Fast Computation: It must be quick to calculate.

   index = HashFunction(Key) (mod TableSize)

Here's a visual representation of how a hash function maps keys to indices in a hash table:

The Challenge: Collisions
A collision occurs when two different keys hash to the same index in the hash table. Since the index space is smaller than the key space, collisions are unavoidable. Handling them efficiently is the central challenge in hashing.

2. Hashing Techniques: Collision Resolution
There are two primary strategies for resolving collisions:

2.1. Separate Chaining (Open Hashing)
In this technique, each bucket (index) in the hash table array holds a pointer to a linked list (or a similar dynamic structure, like a balanced binary search tree in modern Java).

How it Works: When a collision occurs, the new key-value pair is simply added to the linked list at that index.
Pros: Simple to implement, never runs out of space, and performance degrades gracefully as the load factor increases.
Cons: Requires extra space for pointers, and traversing the linked list can degrade performance to O(N) in the worst case (where N is the number of elements).

2.2. Open Addressing (Closed Hashing)
In open addressing, all elements are stored directly within the hash table array itself. When a collision occurs, the algorithm probes(searches) for the next available empty slot.
Common probing techniques include:

Linear Probing: Searches the next slot sequentially:

          index = (hash + i) (mod TableSize)

Quadratic Probing: Searches slots at quadratic intervals:

           index = (hash + i^2) (mod TableSize)

Double Hashing: Uses a second hash function to determine the step size for probing.
Pros: Better cache performance (elements are stored contiguously), no need for external data structures (like linked lists).
Cons: Prone to clustering (groups of filled slots), requires careful load factor management, and deletion can be complex.

3. Hash Table and Hash Map: Clarified
A Hash Table is the generic data structure that implements the principle of hashing to store key-value pairs.

A Hash Map is an implementation of the Hash Table concept, typically referring to the specific class implementation in various programming languages (e.g., HashMap in Java).

Load Factor and Rehashing
The Load Factor (α) is a critical metric:

\text{α} = \frac{\text{Number of Entries}}{\text{Table Size}}

If the load factor gets too high (typically >0.75), collisions become frequent, and performance degrades. To maintain near O(1) performance, the Hash Table undergoes Rehashing (or resizing). This involves:

Creating a new, larger internal array (e.g., double the current size).

Iterating through all existing entries.

Re-calculating their hash codes and inserting them into the new, larger array. This process is an O(N) operation, which is why it's done infrequently.

4. Hashing in Java: hashCode() and equals()
Java's collection framework heavily relies on hashing, primarily through the java.util.Map interface and its implementing classes like HashMap.

The Java Hashing Contract
For any custom object to be used effectively as a key in a HashMap, it must correctly implement the hashCode() and equals() methods:

If two objects are equal according to the equals(Object) method, then calling the hashCode() method on each of the two objects must produce the same integer result.
If the hashCode() method produces the same integer result for two objects, they are NOT necessarily equal (this indicates a collision).

Example: If you override equals() without overriding hashCode(), a key inserted might hash to index 'X', but when you try to retrieve it later, the default hashCode() (which doesn't consider the new equals() logic) might hash it to a different index 'Y', making the object "un-findable."

Implementation Detail: Java 8+ Enhancement
In Java 8 and later, the internal structure of HashMap was improved. A single bucket that contains a very long linked list (due to numerous collisions, which degrades lookup to O(N)) is dynamically converted into a **Balanced Binary Search Tree (specifically a Red-Black Tree) **when the number of elements in the chain exceeds a certain threshold (usually 8). This upgrade improves the worst-case time complexity of lookup, insertion, and deletion from O(N) to O(logN).

5. Java's Map Implementations: HashMap vs. Hashtable

While both classes implement the Map interface and use the hashing principle, they have key differences that dictate their use cases:

Feature	HashMap (Recommended for modern code)	Hashtable (Legacy Class)
Synchronization	Non-synchronized (Not thread-safe)	Synchronized (Thread-safe)
Performance	Faster (No overhead of synchronization)	Slower (Synchronization overhead)
Nulls	Allows one null key and multiple null values	Does not allow null keys or null values
Iteration	Uses Iterator (Fail-Fast)	Uses Enumerator and Iterator (Enumerator is not Fail-Fast)
Inheritance	Extends AbstractMap	Extends Dictionary
Primary Use	Single-threaded environments, high-performance needs	Legacy code or when a simple, fully synchronized map is absolutely required

Code Example: HashMap in Action

Here's a basic Java code snippet demonstrating the use of HashMap:

Java

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        // Declaring a HashMap
        Map<String, Integer> studentScores = new HashMap<>();

        // Adding key-value pairs
        studentScores.put("Alice", 95);
        studentScores.put("Bob", 88);
        studentScores.put("Charlie", 92);
        studentScores.put("David", 88); // David also has a score of 88

        System.out.println("Student Scores: " + studentScores);
        // Output: Student Scores: {Alice=95, Charlie=92, Bob=88, David=88} (Order not guaranteed)

        // Getting a value
        int bobScore = studentScores.get("Bob");
        System.out.println("Bob's score: " + bobScore); // Output: Bob's score: 88

        // Updating a value
        studentScores.put("Alice", 97);
        System.out.println("Alice's new score: " + studentScores.get("Alice")); // Output: Alice's new score: 97

        // Checking if a key exists
        boolean hasCharlie = studentScores.containsKey("Charlie");
        System.out.println("Does Charlie exist? " + hasCharlie); // Output: Does Charlie exist? true

        // Checking if a value exists
        boolean hasScore90 = studentScores.containsValue(90);
        System.out.println("Is there a student with score 90? " + hasScore90); // Output: Is there a student with score 90? false

        // Removing a key-value pair
        studentScores.remove("David");
        System.out.println("Student Scores after removing David: " + studentScores);
        // Output: Student Scores after removing David: {Alice=97, Charlie=92, Bob=88}

        // Iterating through the HashMap
        System.out.println("\nIterating through student scores:");
        for (Map.Entry<String, Integer> entry : studentScores.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        /*
        Output:
        Alice: 97
        Charlie: 92
        Bob: 88
        */
    }
}

Code Example: Hashtable in Action
And here's how you'd use a Hashtable. Notice the similar API but with the restrictions mentioned (no nulls) and its synchronized nature.

Java

import java.util.Hashtable;
import java.util.Map;
import java.util.Enumeration; // For legacy iteration

public class HashtableExample {
    public static void main(String[] args) {
        // Declaring a Hashtable
        Hashtable<String, String> capitalCities = new Hashtable<>();

        // Adding key-value pairs
        capitalCities.put("USA", "Washington D.C.");
        capitalCities.put("France", "Paris");
        capitalCities.put("Japan", "Tokyo");
        capitalCities.put("Germany", "Berlin");

        System.out.println("Capital Cities: " + capitalCities);
        // Output: Capital Cities: {Japan=Tokyo, USA=Washington D.C., Germany=Berlin, France=Paris} (Order not guaranteed)

        // Getting a value
        String usaCapital = capitalCities.get("USA");
        System.out.println("Capital of USA: " + usaCapital); // Output: Capital of USA: Washington D.C.

        // Attempting to add a null key (will throw NullPointerException)
        try {
            // capitalCities.put(null, "Invalid");
        } catch (NullPointerException e) {
            System.out.println("Cannot add null key to Hashtable: " + e.getMessage());
        }

        // Attempting to add a null value (will throw NullPointerException)
        try {
            // capitalCities.put("Spain", null);
        } catch (NullPointerException e) {
            System.out.println("Cannot add null value to Hashtable: " + e.getMessage());
        }

        // Iterating through the Hashtable using Enumeration (legacy way)
        System.out.println("\nIterating through capital cities (using Enumeration):");
        Enumeration<String> keys = capitalCities.keys();
        while (keys.hasMoreElements()) {
            String key = keys.nextElement();
            System.out.println(key + ": " + capitalCities.get(key));
        }
        /*
        Output:
        Japan: Tokyo
        USA: Washington D.C.
        Germany: Berlin
        France: Paris
        */

        // Iterating through the Hashtable using Map.Entry (modern way, also works)
        System.out.println("\nIterating through capital cities (using Map.Entry):");
        for (Map.Entry<String, String> entry : capitalCities.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

The Thread-Safe Alternative
For thread-safe operations in modern Java, the preferred choice is usually ConcurrentHashMap, which offers much higher performance and better concurrency than the legacy Hashtable by using a more granular locking mechanism.

Why I’m Starting My Debt-Free Journey (While Learning to Code)

Gurpreet — Mon, 20 Oct 2025 15:30:54 +0000

I’ve always believed growth happens when you face your truth — and here’s mine: I have debt, and I’m determined to clear it.

As a single mom and computer science graduate, my days are a mix of cooking, teaching my daughter, managing bills, and now… learning DSA (Data Structures & Algorithms).

I started this blog to document two parallel journeys — becoming debt-free and becoming a better coder. Both require discipline, patience, and problem-solving.

Some days, the numbers in my bank app look as confusing as a nested loop — but just like in coding, I’m learning to break big problems into smaller ones.

Every post here will be an honest update — about my progress, my struggles, and small victories. If you’re trying to improve your finances or tech skills too, let’s walk this path together. 💪

Here’s to coding cleaner — and living freer.