3. Longest Substring Without Repeating Characters (Medium)

https://leetcode.com/problems/longest-substring-without-repeating-characters/

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

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solutions

class Solution {

    // Non-Repeating Character Substring (NRCS)

    // This problem solving idea is ingenious that it reduce the time complexity from O(n^2) to O(n)
    // with the use of an array which is used to keep track of the last index of the given char.

    // Walk through the array, at one point, you visit char x, if you find x not appears before, you
    // could deems it as a non-repeating substring. If it occurs previously, there are following two
    // situations.

    // 1. Take string "abcdefgc" as an example, when pointer locates at the tail char 'c', you will find
    // there is another 'c' at index 2, so the max length non-repeating substring is defgc.

    // 2. Take string "abcddefgc" as an example, pointer still locates at the tail char 'c', precious 'c'
    // at index 2. However, the max length non-repeating substring turns to be defgc. The reason is that
    // the counting work starts from the second d because of the prior repeated d.

    // To sum up, when you meet a repeating char, it is not a must to start over the counting, which
    // depends on the specific cases.

    public int lengthOfLongestSubstring(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }

        int len = str.length();

        int[] visited = new int[256];

        //  Initialize the visited array as -1, -1 is used to indicate that character has not been visited yet.
        Arrays.fill(visited, -1);

        // length of max NRCS substring
        int maxLen = 0;

        // previous index
        int prevIndex;

        // length of current NRCS substring
        int curLen = 0;

        for (int i = 0; i < len; i++) {
            prevIndex = visited[str.charAt(i)];

            // Current character is not present in the already processed substring.
            if (prevIndex == -1) {
                curLen++;
            }
            // It is not part of the current NRCS, ignore it and increase curLen
            else if (i - curLen > prevIndex) {
                curLen++;
            }
            // If the current character is present in currently considered NRCS, then update NRCS
            // to start from the next character of the prevIndex.
            else {
                curLen = i - prevIndex;
            }

            // Also, when we are changing the NRCS, we should also check whether length of the previous
            // NRCS is greater than maxLen or not.
            if (curLen > maxLen) {
                maxLen = curLen;
            }

            // update the index of current character
            visited[str.charAt(i)] = i;
        }

        return maxLen;
    }
}

Incorrect Solutions

class Solution {

    // This solution exceeds the time limit.

    // Walk through all the possible length from 2 to s.length(). Use a HashMap to keep the length and
    // possible ranges.

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int len = s.length();

        Map<String, Integer> visited = new HashMap<>();
        for (int i = 0; i < len; i++) {
            visited.put(i + "#" + i, 1);
        }

        // Window size starts from 2 to len
        for (int ws = 2; ws <= len; ws++) {

            // Iterate the chars from 0, and the window tail should not exceed i+wws-1
            for (int i = 0; i < len - ws + 1; i++) {

                // Window [i,i+ws-2] is a preceding window that 1 element less than current
                // window [i, i+ws-1]. If preceding window contains duplicates, it indicates
                // current window also has.

                String pw = i + "#" + (i + ws - 2);
                if (!visited.containsKey(pw)) {
                    continue;
                }

                String cw = i + "#" + (i + ws - 1);

                // s.substring(start, end) where end is exclusive

                if (!s.substring(i, i + ws - 1).contains(s.charAt(i + ws - 1) + "")) {
                    // if doesn't contain duplicates, increase the distinct char number
                    visited.put(cw, visited.get(pw) + 1);
                }
            }
        }

        int max = 0;
        for (String key : visited.keySet()) {
            if (visited.get(key) > max) {
                max = visited.get(key);
            }
        }

        return max;
    }
}

References

  1. https://www.geeksforgeeks.org/length-of-the-longest-substring-without-repeating-characters/
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-02-24 22:41:42

results matching ""

    No results matching ""