algoadvance

Leetcode 3090. Maximum Length Substring With Two Occurrences

Problem Statement

You are given a string, and you are required to find the maximum length of the substring that contains exactly two distinct occurrences of the same character (that is, one character appears at least twice).

Clarifying Questions

1. Input Constraints: Are there any constraints on the length of the string or the characters it can contain?

   • Assumption: The length of the string is between 1 and 10^5, and it consists of lowercase English letters.
2. Edge Cases:
   • A string with all unique characters (e.g., “abcdef”).
   • A string where one character is repeated many times (e.g., “aaaaa”).

3. Output Format: Should we return the length of such a substring, or the actual substring itself?

   • Assumption: We are to return the maximum length of the substring.

Strategy

1. Track Character Positions: Use a HashMap to store the positions of each character.
2. Iterate through Characters: As we iterate through the string, update the positions of each character in the HashMap.
3. Calculate Distances: For each character that appears more than once, calculate the distance between the first and last occurrence.
4. Update Maximum Length: Keep track of the maximum length found.

Approach

1. Initialize a HashMap to store character positions and another variable to track the maximum length.
2. Iterate through the string to populate/update the HashMap (store the first and last position of each character).
3. Compute Maximum Length: For each character in the HashMap, compute the distance between the first and last occurrence and update the maximum length accordingly.
4. Return the Maximum Length found.

Code

import java.util.HashMap;

public class MaxLengthSubstringTwoOccurrences {
    public static int maxLengthSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        HashMap<Character, Integer[]> charPositions = new HashMap<>();
        int maxLength = 0;

        // Populate the HashMap with character positions.
        for (int i = 0; i < s.length(); i++) {
            char currentChar = s.charAt(i);
            if (!charPositions.containsKey(currentChar)) {
                charPositions.put(currentChar, new Integer[] {i, i});
            } else {
                charPositions.get(currentChar)[1] = i;
            }
        }

        // Calculate the maximum length.
        for (Integer[] positions : charPositions.values()) {
            if (positions[0] != positions[1]) {  // The character has appeared more than once.
                int length = positions[1] - positions[0] + 1;
                maxLength = Math.max(maxLength, length);
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        String testString = "ababc";
        System.out.println("Maximum Length: " + maxLengthSubstring(testString));  // Output should be 5.
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the string. We make a single pass over the input string to populate the HashMap and another pass over the HashMap entries to compute the maximum length.
• Space Complexity: O(1) auxiliary space for the character positions, but with the added space for the HashMap, it becomes O(k), where k is the number of distinct characters (at most 26 for lowercase English letters).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?