寻找最长不重复字符子串 – Java

huangapple go评论73阅读模式
英文:

Find the Longest Substring without Repeating Characters - Java

问题

public int lengthOfLongestSubstring(String s) {
    // Using a set to track characters in the current substring
    Set<Character> charSet = new HashSet<>();
    
    int maxLength = 0; // To store the length of the longest substring
    int head = 0; // Pointer for the start of the current substring
    
    for (int tail = 0; tail < s.length(); tail++) {
        char currentChar = s.charAt(tail);
        
        // If the character is already in the set, remove characters from the head of the substring
        // until the current character is no longer in the set
        while (charSet.contains(currentChar)) {
            charSet.remove(s.charAt(head));
            head++;
        }
        
        // Add the current character to the set and update maxLength
        charSet.add(currentChar);
        maxLength = Math.max(maxLength, tail - head + 1);
    }
    
    return maxLength;
}

Please note that the above code snippet is the corrected version of your solution using the two-pointer technique. It uses a sliding window approach with a set to track the characters in the current substring. The pointers 'head' and 'tail' define the current substring, and as 'tail' moves forward, characters are added to the set. If a character is already in the set, the 'head' pointer moves forward while removing characters from the set until the current character is no longer in the set. This ensures that the substring remains without repeating characters. The maxLength is updated whenever a longer substring is found.

Feel free to integrate this code into your solution and test it against the given test cases and the ones you previously mentioned.

英文:

I was trying to solve a leetcode question but my solution is not returning the correct value for one of the test cases. I wanted to implement the two-pointer technique for this solution (if im using the technique wrong, advice is welcome on explaining the proper way to do it). The details are below:

Leetcode Question Title:

> Longest Substring Without Repeating Characters.

Question:

> Given a string, find the length of the longest substring without repeating characters. ( return int )

My Solution:

    public int lengthOfLongestSubstring(String s) {
		//place holder for me to create a &quot;sub-string&quot;
        String sub = &quot;&quot;;
		
		//counter variable to count the characters in the substring
        int count = 0;
        int maxCount = 0;
        
		//my attempt at a TWO POINTER TECHNIQUE
        //pointers - to determine when the loop should break
        int head = 0;
        int tail = s.length();
		
		//this variable was intended to be used with the &quot;indexOf&quot; method, as the &quot;start from&quot; index...
        int index = 0;
        
        while(head &lt; tail){
			//check if the next character in the string was already added to my substring.
            int val = sub.indexOf(s.charAt(head), index);
			
			//we proceed if it is -1 because this means the substring didnt previously contain that character
            if(val == -1){
				//added character to my substring
                sub+= s.charAt(head);
                count++;
                head++;
            } else {
				//reset data to default conditions, while continuing at the &quot;head index&quot; and check the rest of the substring
                count = 0;
                sub =  &quot;&quot;;
            }
			//determine what the length of the longest substring.
            maxCount = count &gt; maxCount ? count : maxCount;
        }
        return maxCount;
    }

I passed the test cases:

&gt; &quot;&quot; = expect 0
&gt; &quot; &quot; = expect 1
&gt; &quot;abcabcbb&quot; = expect 3
&gt; &quot;bbbbb&quot; = expect 1
&gt; &quot;pwwkew&quot; = expect 3
&gt; &quot;aab&quot; = expect 2

I failed test cases:

&gt; &quot;dvdgd&quot; = expect 3, but got 2
&gt; &quot;dvjgdeds&quot; = expect 5, but got 4
&gt; &quot;ddvbgdaeds&quot; = expect 6, but got 4

Possible Issues:

> I believe the issue occurred because it moves pass the index with "v", and then processes the substring "dg". So I attempted to change the solution, but fixing that issue caused all my other cases to return errors so I figured that attempt at a fix should be tossed out.

What I have also tried:

> I also attempted to manipulate the "indexOf" method to change the start index, whenever the character was found in the string. This however generated an infinite loop.

I have been trying to solve this problem for a few hours and I am stomped. So any help would be appreciated greatly. And please be detailed with your explanation if you can, I am very new to DSA and programming, thank you greatly. If more information from me is needed, please let me know am I will try to answer.

答案1

得分: 1

public static int lengthOfLongestSubstring(String s) {
    String sub = "";  // 用于创建“子字符串”的占位符

    int count = 0;
    int maxCount = 0;

    int head = 0;
    int tail = s.length();

    int index = 0;

    while (head < tail) {
        int val = sub.indexOf(s.charAt(head)); // 搜索整个子字符串

        if (val == -1) {
            sub += s.charAt(head);
            count++;
            head++;
            maxCount = count > maxCount ? count : maxCount;
            System.out.println(sub); // 看看目前为止得到了什么
        } else {
            count = 0;
            sub = "";
            head = index + 1;
            index++;
        }
    }
    return maxCount;
}
英文:

Well, here you go:

public static int lengthOfLongestSubstring(String s) {
    //place holder for me to create a &quot;sub-string&quot;
    String sub = &quot;&quot;;
    
    //counter variable to count the characters in the substring
    int count = 0;
    int maxCount = 0;
    
    //my attempt at a TWO POINTER TECHNIQUE
    //pointers - to determine when the loop should break
    int head = 0;
    int tail = s.length();
    
    //this variable shows where to start from 
    int index = 0;
    
    while(head &lt; tail){
        //check if the next character in the string was already added to my substring.
        int val = sub.indexOf(s.charAt(head)); //search whole substing
        
        //we proceed if it is -1 because this means the substring didnt previously contain that character
        if(val == -1){
            //added character to my substring
            sub+= s.charAt(head);
            count++;
            head++;
            //determine what the length of the longest substring.
            maxCount = count &gt; maxCount ? count : maxCount;
            System.out.println(sub); //let&#39;s see what we got so far
        } else {
            //reset data to default conditions, while continuing at the &quot;head index&quot; and check the rest of the substring
            count = 0;
            sub =  &quot;&quot;;
            head=index+1; //begin from the next letter 
            index++; //move
        }
        
        
    }
    return maxCount;
}

huangapple
  • 本文由 发表于 2020年8月20日 18:50:21
  • 转载请务必保留本文链接:https://go.coder-hub.com/63503473.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定