Need help with the question asked in Josh technology SDE

help
, , ,
1

Question discussion.
Josh technology SDE.
17/01/22

Given a LinkedList, where each node contains small case characters, you are asked to form a strong password using characters from that LinkedList. A strong password’ is the one in which no two characters are repeating. The output password must be a continuous subset of the given LinkedList, Find the length of the strongest password that can be formed using the input LinkedList.
Example 1
Input: s=a>b>c>a>b>c>b>b

Output: 3

Explanation: The answer is abc, with the length of 3.

Example 2:

Input: s->p-w->w->k->e->w

Output: 3

Explanation: The answer is w-k-e, with the length of 3.

Notice that the answer must be a continuous subset, p->w->k->e is a subset and not a continuous subset

Expected Time Complexity: O(n) Expected Space Complexity: 0(1)

@suman_18733097

2 Likes
2

Considering continous subset as a subarray, we just have to print the max length of that subarray which contains distinct elements.

1 Like
3

Yes i got that but what my concern is how to do this in given constraints?
Do you have any approach

4

I think, two pointer method will be helpful.

Create a boolean array (for 26 characters (a-z)) to store true-if they are visited and false-if unvisited.

Consider two pointers as left and right

Initially both pointers will be at starting node.

Start traversing the linked list using right pointer and while traversing, mark that character in boolean array as visited.

While traversing, if you encounter a character that is already visited, start traversing using left pointer till you encounter that visited character, and position that left pointer next to that character
and while this traversal (means while traversing using left), mark those characters as unvisited.

You also have to manage the length variable(answer), like when traversing using right pointer, increment the length and while traversing using left pointer, decrement the length.

As you will be traversing each node twice (one using right and other using left), the complexity is O(n) and space complexity is also O(1) as there are only 26 characters.

6 Likes
5

Thanks, will try this approach.

6

Were you able to solve it?

7

Has anyone done the code?

8

anyone done this kindly share the code