Article From:https://www.cnblogs.com/travelller/p/9124140.html

Find the longest substrings of a string without repeating elements.

 

There are many ways to solve the problem. In general, because Java encapsulates many classes, there are many functions in the class, so it is better than C++.

Solution 1: brute force O (n^3)

  Enumerate each substring O (n^2) to determine whether there is a duplicate element (using the HashSet in Java to judge whether an element is O (1) in the set, determine whether there is a repeating element O (n) in the substring, and unordered_map in the C++ standard template library.Instead), the complexity is O (n^3).

Solution two: sliding windows O (2n)

  Set up a slider with I j starting position, and continue extend the range [I, J]. Also use hashset/unordered_map maintenance. If s[j] does not exist in set, add s[j]J++. Otherwise, judge and record the length of the current substring is the longest, the starting coordinates move to the next position of the last s[j], and the intermediate element is removed from the set. The setting of the initial coordinates is critical, otherwise these elements cannot be removed. Finally, it returns to the longest range.

Solution three:

  The optimization of the solution two. Only update the location of the element in the map (mapping to the set storage), judge whether the s[j] has appeared in the substring by judging the relationship between the s[j] and the starting position, without removing the element, and moving the location of the I directly. Save the removalThe complexity of O (2n) -O (n) =O (n).

Solution four:

  The optimization of the solution three. The map storage mapping pair is not used because the input character set range is limited (256 for extended ascll), so using an array of length 256 can store mappings.

 

Note: when Java is used, the solution three can be implemented with queue without marking the starting position and pressing directly into the element or the pop-up element, but judging whether an element has occurred in the queue or not, because the queue in the c++ standard template library does not support the iterator, so it can not be implemented. JQueue.contains () in AVA can be implemented.

 

Solution three code:

#include <unordered_map>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
        unordered_map <int,int> a;
          int i=0,j=0,ans=0,n=s.length();
          for(;j<n;j++){
              if (a.count(s[j])){
                  auto iter=a.find(s[j]);
                int temp=iter->second;
                  i=temp>i?temp:i;
                  a.erase(s[j]);
              }//if    
              a.insert(pair<int,int>(s[j],j+1));
              ans=(j-i+1)>ans?j-i+1:ans;
          }//for
          return ans;
    }
};

 

When you notice i=j, the substring length is 1, so pay attention to the position meaning of the coordinates.

Similar Posts:

Leave a Reply

Your email address will not be published. Required fields are marked *