The longest substring complexity of letCode without repeating characters O(n)

The longest substring complexity of letCode without repeating characters O(n)

Method 1

When we see this problem, the first method we think of is to store each symbol (subscript and char symbol) in order with LinkList. When we traverse to a certain character, we can judge whether the current character has been stored in the linked list.
(1) If the character is not in the list, it will be added to the end of the list
(2) The character is already in the linked list. Judge the current size of the linked list. If the value is greater than max, update the max value. Remove the node where the character is located and the nodes in front of it from the list, and then add the character and its position information node in the string to the end of the list
This eventually gets the maximum value, but the method times out. The code is as follows

class Solution {
class Node{
   	 char c;
   	 int index;
   	 public Node(char c,int index) {
   		 this.c=c;
   		 this.index=index;
   	}
   	 @Override
   	public boolean equals(Object obj) {
   		 
   		if (obj instanceof Node) {
   			
   		}
   		return super.equals(obj);
   	}
    }
    private int getIndex(List<Node> nodes,char v) {
   	    int i=0;
   		for (Node n:nodes) {
   			if (n.c==v) {
   				return i;
   			}
   			i++;
   		
   		}
   		return -1;
   	}
   		
    public int lengthOfLongestSubstring(String s) {
   	 char[] str=s.toCharArray();
   	 List<Node> nodes=new LinkedList<>();
//		  Map< Character, Integer> map=new HashMap<Character, Integer>();
   	  int len=0,max=0;
   	  
   	  for(int i=0;i<str.length;i++) {
   		  int index=getIndex(nodes, str[i]);
   		  if (index!=-1) {

   			  if(len>max) {
   				  max=len;
   			  }
   			  nodes=nodes.subList(index+1, nodes.size());
   			  len=1+nodes.size();
   			  nodes.add(new Node(str[i],i));
//				  System.out.println("("+i+","+str[i]+"+)"+"node = ");
//				  for (Node n:nodes){
//				  	System.out.print(n.c+" ");
//				  }
//				  System.out.println("len="+len);
   		  }else {
   			  len++;
   			  nodes.add(new Node(str[i],i));
   		  }
   	  }
   	  if(len>max)max=len;
   	  
         return max;
   }

   
}

Method two

When you see the overtime data, you find that the basic characters are all in 128 ASCII, so you want to directly use an array of 128 length to store. The default value of the array is - 1, that is, it has not been accessed.
When the current character is scanned
(1) If the character has been accessed and is in the current range, compare len and Max universities and update the max value. Reset the range to the next bit accessed last time, and change the subscript the character points to to the current subscript.
(2) The character has not been accessed or is not in the current range. Update the subscript it points to to the current subscript.

The speed of random access can be considered as o(1). Traversal character o (n)
So the time complexity is O(n)
The code is as follows

public class Soulution {

  public int lengthOfLongestSubstring(String s) {
	 	int max=0,len=0;
		char[] str=s.toCharArray();
	 	int cArray[]=new int[128];
//	 	Currently accessed subscript the leftmost character subscript of the current range
	 	int currentIndex=0,leftIndex=-1;
		for (int i=0;i<cArray.length;i++)cArray[i]=-1;
		for (char c:str) {
//			Subscript where the current character was last accessed
			int lastVisitIndex =cArray[(short)c];
//			 The character has been accessed, and the last accessed position of the character is within the current range
			if(lastVisitIndex!=-1 && lastVisitIndex>=leftIndex){
				if (len>max)max=len;
				leftIndex=lastVisitIndex+1;
				len=currentIndex-leftIndex+1;
			}else {
				len++;
			}
			cArray[(short)c]=currentIndex;
			currentIndex++;
		}
		if(len>max)max=len;
	 	return max;
	}

Published 9 original articles, praised 0, visited 4052
Private letter follow

Tags: ascii

Posted on Wed, 29 Jan 2020 01:11:24 -0800 by aris1234