Punit Jain

Campbell Ritchie wrote:Congratulations on both counts.

Thank you!

That's helpful. I have accepted the verbal offer and yet to receive the formal offer in the email. The HR is expected to call me on Monday or Tuesday. Should I discuss the time off plan before accepting the offer by email? Or should I first accept and then call her again to discuss? Not sure if it matters.

Tim Holloway wrote:I would get approval first. Taking time off that close to your hire date would generally be a cause for concern if they didn't know far enough in advance.

Good fortune, though. I got married on a Saturday and started a new job on Monday. Never got a honeymoon.

Thanks. Should I also let them know that if two weeks is it's not possible then I can make it 1 week? Do you think that would still be concerning?

You should plan a honeymoon in 2021.  

Hi Guys,

I hope all is well and everyone is staying safe. I was planning to change my employer and recently got an offer from one of the big four. My joining date should be sometime in mid-march. I am also getting married in June and would be taking two weeks PTO.

My question is - should I let my new employer know this before my joining? Or it's normal and fine to let them know after joining?

Liutauras Vilda wrote:Cowgratulations, your post has been published in CodeRanch's August 2020 journal.

Thank you.

Campbell Ritchie wrote:Why do you need these counters when you can use Set#size() instead? Please explain how your loop works; I don't understand the logic. I cannot however break your code. Why are you accepting null or empty Strings?

Let's say the input is: "abcabcbb"

It will go into the if condition till the 2nd index. The character at the third index is already present in the set hence it will go into the else block. It will start removing the characters from the set until it encounters that repetitive character (the current value of index 'i'). It will then increment the removevaluecounter and break the while loop. At this point, the set will have only that repetitive character (the current value of index I). It will resume the for loop.

I think the empty string should be size 0, but I can skip the null part.

Piet Souris wrote:@Punit
well done, and have a cow!

thanks so much.    

Piet Souris wrote:
An extra challenge for you: can you extend your method such that it also gives that longest substring, and its starting index?

Sure, how about this:

public static Map<String, Integer> findLongestSubstring(String s) { Set<Character> visitedStrings = new HashSet<>(); Map<String, Integer> uniqueString = new HashMap<>(); int sizeOfLongestNonRepeatingSubstring = 0; int removeValuesCounter = 0; for (int i = removeValuesCounter; i < s.length(); i++) { char currentCharacter = s.charAt(i); if (!visitedStrings.contains(currentCharacter)) { visitedStrings.add(currentCharacter); int currentSize = visitedStrings.size(); if (sizeOfLongestNonRepeatingSubstring < currentSize) sizeOfLongestNonRepeatingSubstring = currentSize; } else { while (removeValuesCounter < i) { if (s.charAt(removeValuesCounter) == currentCharacter) { removeValuesCounter++; break; } visitedStrings.remove(s.charAt(removeValuesCounter)); removeValuesCounter++; } } } uniqueString.put(visitedStrings.toString(), removeValuesCounter); return uniqueString; }

So here is how I am doing it now:

Approach

1. Iterate through the characters in the string.
2. Keep adding the characters to a data structure that accepts unique values.
3. Store the current length of the data structure in memory.
4. Start removing the values from the string as soon as it encounters a duplicate character in the string.
5. Perform step#1 to 4 until it reaches the end of the string.


Implementation

Iterate through the characters in the string and add them to a HashSet until a repetitive character is found. Keep storing the current length in an integer variable. As it encounters a unique character, start removing from the HashSet while maintaining a remove counter variable.

Code

import java.util.HashSet; import java.util.Set; final class LongestSubstringWithoutRepeating { /** * Finds the length of longest substring without repeating characters in the * given string. <br /> * * For example: <br /> * * <pre> * <b>Input:</b> "abcabcbb" * <b>Output:</b> 3 * <b>Explanation:</b> The answer is "abc", with the length of 3. * </pre> * * @param s the array to search * @return the length of longest non repeating string otherwise 0 */ public static int findLongestSubstring(String s) { if (s == null || s.isEmpty()) { return 0; } Set<Character> visitedStrings = new HashSet<>(); int sizeOfLongestNonRepeatingSubstring = 0; int removeValuesCounter = 0; for (int i = 0; i < s.length(); i++) { char currentCharacter = s.charAt(i); if (!visitedStrings.contains(currentCharacter)) { visitedStrings.add(currentCharacter); int currentSize = visitedStrings.size(); if (sizeOfLongestNonRepeatingSubstring < currentSize) sizeOfLongestNonRepeatingSubstring = currentSize; } else { while (removeValuesCounter < i) { if (s.charAt(removeValuesCounter) == currentCharacter) { removeValuesCounter++; break; } visitedStrings.remove(s.charAt(removeValuesCounter)); removeValuesCounter++; } } } return sizeOfLongestNonRepeatingSubstring; } public static void main(String[] args) { System.out.println(LongestSubstringWithoutRepeating.findLongestSubstring("abcabcbb")); // Works fine System.out.println(LongestSubstringWithoutRepeating.findLongestSubstring("bbbbb")); // Works fine System.out.println(LongestSubstringWithoutRepeating.findLongestSubstring("aab")); // Works fine System.out.println(LongestSubstringWithoutRepeating.findLongestSubstring("pwwkew")); // Works fine System.out.println(LongestSubstringWithoutRepeating.findLongestSubstring("Campbell Ritchie")); // Works fine System.out.println(LongestSubstringWithoutRepeating.findLongestSubstring(null)); // Works fine System.out.println(LongestSubstringWithoutRepeating.findLongestSubstring("")); // Works fine } }

Campbell Ritchie wrote:But what about the values? What are you doing with the values? Hint: nothing. So why are you using a map? Why don't you use other data structures/types?

Yes, I should use a different data structure that takes unique values.

Campbell Ritchie wrote:You mean O(1) time complexity? There are other data structures giving O(1) time complexity too. And some maps run in O(logn) time complexity. That is for the put() method, at least.

Actually, I meant that I could do it in just one loop.

Campbell Ritchie wrote:But what about the values? What are you doing with the values? Hint: nothing. So why are you using a map? Why don't you use other data structures/types?

Yes, I should use a different data structure that takes unique values.

Campbell Ritchie wrote:You mean O(1) time complexity? There are other data structures giving O(1) time complexity too. And some maps run in O(logn) time complexity. That is for the put() method, at least.

Actually, I meant that I could do it in just one loop.

Liutauras Vilda wrote:
Is that what your string shortening achieves?
s = s.substring(currentSize, s.length() - 1);

expected:
pwwkew
wwkew
wkew
kew
...

Got it. Here is the updated code:
public static int findLongestSubstring(String s) { Map<Character, Integer> visitedString = new HashMap<>(); int sizeOfLongestNonRepeatingSubstring = 0; for (int i = 0; i < s.length(); i++) { char currentCharacter = s.charAt(i); if (visitedString.put(currentCharacter, i) != null) { int currentSize = visitedString.size(); if (sizeOfLongestNonRepeatingSubstring < currentSize) { sizeOfLongestNonRepeatingSubstring = currentSize; i = currentSize + 1; } } } return sizeOfLongestNonRepeatingSubstring; }

Liutauras Vilda wrote:

Punit Jain wrote:Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Apart from somewhere incorrect logic what Campbell already mentioned to you, your solution doesn't seem to adhere to the requirements you posted. I've bolded that part.

As per the first line "Given a string, find the length of the longest substring without repeating characters." Also, the return type in the method signature on leetcode is int. So I think that they are expecting the length as I can't change the method signatures.

By this -  "pwke" is a subsequence and not a substring - I think they meant that it should be the length of substring and not a subsequence. But yeah, they should have added the length word in the last line to avoid confusion.

Campbell Ritchie wrote:

Punit Jain wrote:Keep appending the character to the map as map keys.

Why did you say “map”? Anyway, that is an implementation detail, which shouldn't be included in the logic.

I thought to use a map because the keys in map should be unique. When the map encounters a repeating key, it replaces the value of the same existing key. Based on the problem, this way I will know that I need to break/pause once I encounter the same key and store the length to a variable. Another reason I chose a map so that I get o(n).

Campbell Ritchie wrote:

Punit Jain wrote:As soon as I reach to a character that's already added to the map . . .

You mean when you encounter a character already recorded.

Yes, thanks for the correction.

Campbell Ritchie wrote:

Punit Jain wrote:a temp variable.

Another implementation detail.

You mean, I am mixing up logic with the implementation details? I should first build the logic without selecting the specific data structures and then the implementation details (i.e. selecting the data structures)?

Campbell Ritchie wrote:

Punit Jain wrote:. . . remove the already visited characters . . .

Please explain what you mean about removal? Why don't you simply start from the next character? What does line 21 do?

By removal - I meant shortening the string by taking out the already visited string from the original string and start again from index 0. Yes, I can also start with the next character and that would be better as I save the call to substring(). I assume you meant line# 31 then it removes (substring) the already visited string from the actual string and then the next line is to reset the index to 0. Like the following:

for (int i = 0; i < s.length(); i++) { char currentCharacter = s.charAt(i); if (visitedString.put(currentCharacter, i) != null) { int currentSize = visitedString.size(); if (sizeOfLongestNonRepeatingSubstring < currentSize) { sizeOfLongestNonRepeatingSubstring = currentSize; i = currentSize; } } }

Campbell Ritchie wrote:I think you are shortening the text from its beginning wrongly.

Did you mean this? s = s.substring(currentSize, s.length() - 1);

Campbell Ritchie wrote:Have a possible solution, but I am keeping it hidden.

My JShell wrote:SubstringFinder.main( "abcabcbb",  "bbbbb", "pwwkew");
Longest substring = “abc”; length =    3
Longest substring = “b”; length =      1
Longest substring = “wke”; length =    3

Yup, want to improve my logic building.