I don't see where is mistake

Question about the task

Unique substrings

Java Collections, Level 9, Lesson 9

Resolved

I think my logic is good but I suppose something I don't see is wrong

Implement the lengthOfLongestUniqueSubstring method so that it returns the length of the longest substring without repeated characters in the string passed as an argument.
For example, for "a123bcbcqwe", it should return 6. For "ttttwt", it should return 2.
If the passed string is empty or null, return 0.

Requirements:

The lengthOfLongestUniqueSubstring method must return the length of the substring with the maximum number of unique characters.
The lengthOfLongestUniqueSubstring method must return 0 for an empty string or null.
The lengthOfLongestUniqueSubstring method must be public.
The lengthOfLongestUniqueSubstring method must be static.

package com.codegym.task.task39.task3901; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; /* Unique substrings */ public class Solution { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); System.out.println("Please enter your string: "); String s = bufferedReader.readLine(); System.out.println("The longest unique substring length is: \n" + lengthOfLongestUniqueSubstring(s)); } public static int lengthOfLongestUniqueSubstring(String s) { if (s == null || s.isEmpty()) return 0; Set<Character> charsSet = new LinkedHashSet<>(); char[] charsArr = s.toCharArray(); int longestLength = 0; int next = 0; for (int i = 0; i < charsArr.length; i++) { if (charsSet.add(charsArr[i]) == false) { if (longestLength < charsSet.size()) { longestLength = charsSet.size(); } charsSet.clear(); i = ++next; } } return longestLength; } }

Comments (8)

Popular
New
Old

You must be signed in to leave a comment

Thomas

Level 41 , Bayreuth, Germany

22 November 2023, 11:39

solution

eg. try: abcdbef I'd expect it to be 5 (for cdbef)

matemate123

Level 50 , Kraków, Poland

22 November 2023, 15:30

Of course I get now where problem is, I don't set program for situation when last substring is the longest and it have not repetition. It's clear why IT have testing branch :D Thanks Thomas like always you saving my ass.

matemate123

Level 50 , Kraków, Poland

22 November 2023, 15:45

I rebuild it a little but still something wrong:

public static int lengthOfLongestUniqueSubstring(String s) {
    if (s == null || s.isEmpty())
        return 0;

    Set<Character> charsSet = new LinkedHashSet<>();
    char[] charsArr = s.toCharArray();
    int longestLength = 0;

    int next = 0;
    for (int i = 0; i < charsArr.length; i++) {
        boolean isAdded = charsSet.add(charsArr[i]);
        if (longestLength < charsSet.size()) {
            longestLength = charsSet.size();
        }
        if (!isAdded) {
            charsSet.clear();
            if (next < charsArr.length)
                i = ++next;
        }
    }

    return longestLength;
}

I have no ideas

Thomas

Level 41 , Bayreuth, Germany

22 November 2023, 17:53

solution

when you have smth like abac, then you stop at the 2nd a and have the first result ab. When you now continue with the second a you end up with an ac which also has a length of 2. However that's not what you expect as result. You want to get bac with a length of 3. But what if you not continue after the entire found first string ab (at index 2) but instead after the first char of the first string (first char is a with index 0, now you proceed to index 1 which is b and from here you start an entirely new search which will finally find bac. I like doing such things using arrays so here is my approach, I do not know if it'll validate though.

public static int lengthOfLongestUniqueSubstring(String s) {
    if (s == null) {
        return 0;
    }

    int
            outerPos = 0,
            pos,
            maxSeq = 0,
            thisSeq;
    int[]
            chars;

    while (outerPos < s.length()) {
        chars = new int[127]; // consider only the first 128 ascii values otherwise use a set, map etc.
        thisSeq = 0;
        pos = outerPos++;

        while(pos < s.length() && chars[s.charAt(pos++)]++ == 0) {
            // if to confusing remove the above two postfix increment and the below prefix increment operator and
            // instead uncomment
            // chars[s.charAt(pos)]++;
            // pos++;
            // thisSeq++;

            maxSeq = Math.max(maxSeq, ++thisSeq);
        }
    }

    return maxSeq;
}

matemate123

Level 50 , Kraków, Poland

22 November 2023, 20:54

Ok I see, you're very good tester. I think my approach to this task was wrong, and not my day too. Firstly I try do it my self, and secondly I analize your code. Thanks a lot man, you're so powerful programmer!

matemate123

Level 50 , Kraków, Poland

22 November 2023, 21:05

When you gave me example "abac" I was thinking "why my method isn't working". Bug was so stupid:

public static int lengthOfLongestUniqueSubstring(String s) {
        if (s == null || s.isEmpty())
            return 0;

        Set<Character> charsSet = new LinkedHashSet<>();
        char[] charsArr = s.toCharArray();
        int longestLength = 0;

        int next = 1 // start from one, must be --> next = 0;
        for (int i = 0; i < charsArr.length; i++) {
            boolean isAdded = charsSet.add(charsArr[i]);
            if (longestLength < charsSet.size()) {
                longestLength = charsSet.size();
            }
            if (!isAdded) {
                charsSet.clear();
                if (next < charsArr.length)
                    i = next++;
                  // I forget that when next = 1, I get here i = 1
// (it's what I want) but in next iteration for loop add another +1 to i   -_-
            }
        }

        return longestLength;
    }

So stupid mistake but now I'll analize your Solution for penance.

matemate123

Level 50 , Kraków, Poland

22 November 2023, 21:21

PS: "// if to confusing remove the above two postfix increment and the below prefix increment operator" I was confused by the way :D First time I see postfix, and another postfix in one line. Equilibristic approach :) 🤙🤝 Man your way of thinking is so nerdy but it's definitely compliment if we talk about programmers. My mind burn.

Thomas

Level 41 , Bayreuth, Germany

22 November 2023, 22:10

Your approch was good. Just that little glitch was stopping you ;) These little tasks always seem to be easy and in the end they are really tricky