DEV Community: Chris Kakos

Leetcode: Longest Substring without Repeating Characters

Chris Kakos — Thu, 17 Jun 2021 20:26:41 +0000

Instruction

Given a string s, find the length of the longest substring without repeating characters.

What is Being Asked?

Write a function that loops through an input string to check for the longest subset of unique characters and return the length of it's size.

example 1: abcdd would return 4 because that's the contiguous amount of unique characters within the contents of the input string.

example 2: bbbbb would return 1 because there is a single unique character.

What Does That Look Like?

I used the Sliding Window technique with a dynamic resize to accomplish this. A Sliding Window is essentially a process for traversing a data structure to compare or modify its contents. The operation looks similar to how an accordion stretches out and releases in or perhaps the movement of a caterpillar.

Note:

Chrome uses {} when logging a Set.
Firefox uses [].

What Do I Need to Solve?

I begin with an edge case that checks if the input string is valid and return 0 if it isn't.

I chose to use a JavaScript Set object as the data structure to apply the Sliding Window technique in my solution. A Set is a collection of unique values of any type. In this case, we'll be working with typestring.

To compare and/or modify the characters of the input string from within the Sliding Window, I'll need two pointers.

I define two variables: i and j and set them each to 0.

I also define a variable: result that will store the value of the longest substring to return and initialize it to 0.

The iteration consists of a nested while loop. The i pointer drives the process. While i is less than the size of the string, each iteration will add the value of i to the Set as long as it doesn't already exist.

It then sets the result value using JavaScripts Math.max() method. This method returns the greater value of the two integers passed to it. After result is set, i increments 1 and the loop continues.

When i gets to a value already stored in the Set, j will remove the value from the window and increment 1 for the next iteration.

Once the while loops complete, the function will return the value stored in longestSubstring.

Solution

Time: O(n) where n is the number of characters in the string.
Space: O(n) where n is the length of the Set.

Conclusion

I hope this explanation of my solution was helpful in your search. This is not the only approach and I am interested to hear other peoples strategy in solving the problem. Feel free to leave a comment and let me know! Thanks for taking the time to read!

Leetcode: Add Two Numbers

Chris Kakos — Wed, 16 Jun 2021 18:55:54 +0000

Instructions

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Before we breakdown what the problem is asking, let's first discuss what a linked list is.

Linked List

A linear data structure of nodes chained together by pointers whose order is not determined by a physical location in memory. Each node in the list contains a data field and a reference to the next node in the list.

A linear data structure? Sounds like an array. Yes, but mostly no. Depending on the programming language, arrays tend to be of fixed size--though not the case in JavaScript. It is also very expensive to modify an array. The space for updating and/or removing elements must be created and shifted depending on which index you're operating on.

The advantages of linked lists attribute to their dynamic size and ease of modification, specifically insertion and deletion.

The disadvantages should be considered as followed: random access is not allowed so you must access elements in sequential order. Extra memory space is required for the pointer on each element of list. Linked lists are not cache friendly being that there is no physical reference point to find a node like an index.

There are 3 types of linked lists: Singly, Doubly and Circular. We'll be working with a Singly Linked List.

Each node is made up of at least two properties:

the data
a pointer which is a reference to the next node in line.

The first node is referred to as the head. If a linked list is empty, the value of the head is null.

What is Being Asked?

Write a function that accepts two arguments:

linked list a
linked list b

Both input lists contain whole numbers and are pointing in reverse meaning they're moving left bound. We must apply basic mathematics and add them together, then return the sum as its own linked list.

What Does That Look Like?

What Do I Need to Solve?

I define 2 variables as pointers: pointerA and pointerB and set them to an input list of their own.

I define 2 more variables as containers for the node values that we need to add: a and b and set them each to 0.

I also define a variable to store a value to carry over 1 like the example above.

We need to return a new linked list. I define a result variable and set it to a newly instantiated node list which points the head of the list. Then create an additional variable to represent the currentNode being operated on and point it to the result variable.

I used a while loop that runs until pointerA OR pointerB is not truthy, meaning that it will continue to loop until both lists run out of nodes. Inside of the while block is a series of conditionals explained in the comments.

Solution

Conclusion

I refactored the variable names to read more explicitly in an effort to make clear what is taking place throughout each iteration. Would you have solved it the same or did you go with a different approach? Do you have any suggestions on a refactor that may work better? Drop a comment! I'm interested to hear what you think.

As always thank you for reading and I look forward to interacting and sharing more code!

Leetcode: Two Sum

Chris Kakos — Tue, 15 Jun 2021 23:17:20 +0000

Instructions

Given an array of integers: num and an integer: target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

What is Being Asked?

Write a function that takes two arguments:

an array of integers
an integer

Within the block scope, you need a way to iterate over the values of nums and add the current index value with each of the remaining indices. If the sum of the current index value and the comparison index value are equivalent to the target number, the function should return an array containing the position of both indices. If no conditionals equate to the target number, the function should return false.

What Does That Look Like?

What Do I Need To Solve?

I chose a nested for loop in my solution to iterate over the input array: nums. The outer loop keeps track of the current index value and the inner loop compares the comparison index value(s). If the sum of the outer loop index value and the inner index value equal the target number, it then returns an array with both indices.

Solution

Conclusion

Thank you for taking the time to read. It's with good intent that I share my approach in hopes that it adds a different perspective for anyone looking to get a better understanding of solving algorithmic challenges and building solutions with code.

If that's the case, let me know! Give it a like, drop a comment or feel free to connect with me on Twitter @ch2isk4kos. I'm all about connecting with the community!