Use HashMap to store counts of letters⌗

Two points we should be noticed:

  1. The length of substring should be (right - left) + 1, as one side must be counted.

  2. We must decrese the number in the counts first, and then slide the left window, or we must decrese the wrong one, please compare between Wrong and Correct.

    Wrong

    left++;
counts[s[left]]--;

    Correct

    counts[s[left]]--;
left++;

The full code see:

class Solution {
public:
	int lengthOfLongestSubstring(string s) {
		int left = 0;
		int longest = 0;
		char c;
		map<char, int> counts;

		// for loop to slide the right side of window.
		for (int right = 0; right < s.size(); right++) {
			c = s[right];
			if (counts.find(c) == counts.end()) {
				counts[c] = 0;
			}
			counts[c]++;

			// slide the left side of window to meet the requirements,
			// here is "Without Repeating Characters".
			for (auto iter = counts.begin(); iter != counts.end(); ++iter) {
				if (iter->second > 1) {
					counts[s[left]]--;
					left++;
					break;
				}
			}

			// compare to result.
			longest = max(longest, right - left + 1);
		}
		return longest;
	}
};

See also: An Introduction to Sliding Window Algorithms

Use HashMap to store index of letters⌗

Points that should be noticed:

  1. The whole string without repeating, that will not meet the condition: letter is indexed already.

    • " "
    • "au"
    // no duplicated
if (indices.find(l) != indices.end()) {
	left = indices[l] + 1;
	longest = max(longest, right - left + 1);
}

    In those cases longest will be 0, if this is the only one block to compute the longest.

    Move compute the longest out of the if block, the problem should be sloved.

    // no duplicated
if (indices.find(l) != indices.end()) {
	left = indices[l] + 1;
}
longest = max(longest, right - left + 1);

  2. The left may go backward from a HashTable, and that must be avoid.

    • “abba”
    if (indices.find(l) != indices.end() && indices[l] + 1 > left) {
	left = indices[l] + 1;
}
longest = max(longest, right - left + 1);

    And notice that +1 must exists in the condition, the WRONG edition:

    if (indices.find(l) != indices.end() && indices[l] > left) {
	left = indices[l] + 1;
}
longest = max(longest, right - left + 1);

Finally code:

class Solution {
public:
	int lengthOfLongestSubstring(string s) {
		int left = 0;
		int longest = 0;

		map<char, int> indices;
		for (auto right = 0; right < s.size(); right++) {
			char l = s[right];
			if (indices.find(l) != indices.end() && indices[l] + 1 > left) {
				left = indices[l] + 1;
			}
			longest = max(longest, right - left + 1);
			indices[l] = right;
		}
		return longest;
	}
};

Full with failed:

class Solution {
public:
	int lengthOfLongestSubstring(string s) {

		int left = 0;
		int longest = 0;

		map<char, int> indices;
		for (auto right = 0; right < s.size(); right++) {
			char l = s[right];

			/*
			// failed on string without repeating: " " "au"
			if (indices.find(l) != indices.end()) {
				left = indices[l] + 1;
				longest = max(longest, right - left + 1);
			}
			*/

			/*
			// failed on left go backward: "abba"

			 if (indices.find(l) != indices.end()) {
				 left = indices[l] + 1;
			 }
			 longest = max(longest, right - left + 1);
			*/

			if (indices.find(l) != indices.end() && indices[l] + 1 > left) {
				left = indices[l] + 1;
			}
			longest = max(longest, right - left + 1);
			indices[l] = right;
		}
		return longest;
	}
};

Optimization: use the unordered_map to instead map.

class Solution {
public:
	int lengthOfLongestSubstring(string s) {
		int left = 0;
		int longest = 0;

		unordered_map<char, int> indices;
		for (auto right = 0; right < s.size(); right++) {
			char l = s[right];
			if (indices.find(l) != indices.end() && indices[l] + 1 > left) {
				left = indices[l] + 1;
			}
			longest = max(longest, right - left + 1);
			indices[l] = right;
		}
		return longest;
	}
};