Longest Substring Without Repeating Characters

Problem:

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

Show Tags

Solution:
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char, int> char_set;
        int start = 0, size = s.size();
        int result = 0, max_result = 0;
        
        for (int i = 0; i < size; i++) {
            if (char_set.find(s[i]) != char_set.end()) {
                while (start <= char_set[s[i]])
                    char_set.erase(s[start++]); // clear all before the dup.
            }
            char_set[s[i]] = i;
            max_result = max(max_result, i - start + 1);
        }
        return max_result;
       
    }
};

Complexity: O(2n)

========== Optimized version =====

 new complexity is O(n).

class Solution {

public:

int lengthOfLongestSubstring(string s) {

if (s.size() == 0) {

return 0;

}

int left = 0;

int ans = 0;

unordered_map<char, int> mp;

for (int right = 0; right < s.size(); right++) {

if (mp.count(s[right])) {

// This loop can be removed.

/**

while (left <= mp[s[right]]) {

mp.erase(s[left]);

left++;

}

*/

left = max(left, mp[s[right]] + 1);

}

mp[s[right]] = right;

ans = max(ans, right - left + 1);

}

return ans;

}

};

Remove Linked List Elements

Problem:

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

Solution:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *curr = head;
        // Base case
        while (curr != NULL && curr -> val == val) {
            curr = curr -> next;
            head = curr;
        }
        // Iteration start.
        while (curr != NULL) {
            if (curr -> next != NULL && curr -> next -> val == val)
                curr -> next = curr -> next -> next;
            else
                curr = curr -> next;
        }
        return head;
    }
};

==========

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode() : val(0), next(nullptr) {}

 *     ListNode(int x) : val(x), next(nullptr) {}

 *     ListNode(int x, ListNode *next) : val(x), next(next) {}

 * };

 */

class Solution {

public:

    ListNode* removeElements(ListNode* head, int val) {

        if (head == NULL) {

            return NULL;

        }

        ListNode* dummy = new ListNode(-1);

        ListNode* tmp = dummy;

        while (head != NULL) {

            if (head -> val != val) {

                tmp -> next = head;

                tmp = tmp -> next;

            }

            head = head -> next;

            tmp -> next = NULL;

        }

        return dummy -> next;

    }

};

Happy Number

Problem:

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

• 1² + 9² = 82
• 8² + 2² = 68
• 6² + 8² = 100
• 1² + 0² + 0² = 1

Solution:

class Solution {
public:
    // Since, we don't care about sorted order of keys, we should use unordered data structure instead of ordered(std::map or std::set -> store keys in       // sorted order in binary search tree format: log n insertion, lookup time)
    // And among unordered_map and unordered_set, we'll use unordered_set since we don't need values related to keys in this problem.
    // unordered (set or map) use hashtables internally (not trees), so lookup/insertion time is constant. Drawback is: keys are not sorted as in BST.
    
    bool check_num(int a, unordered_set<int> &set) {
        if (set.find(a) != set.end())
            return true;
        set.insert(a);
        return false;
    }
    bool isHappy(int n) {
        int num = n;
        int new_num =  0;
        unordered_set<int> set;
        while (1) {
            while (n != 0) {
                new_num += pow(n % 10, 2);
                n /= 10;
            }
            if (new_num == 1)
                return true;
            else if (check_num(new_num, set))
                return false;
            n = new_num;
            new_num = 0;
        }
    }
};

Palindrome Number

Problem:

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

Solution:

class Solution {
public:
    // No need to use count function.
    // Mistake was, I used count function earlier, this is a bug. you need divide divisor by 100 in each loop. Test case: 1000021.
    int count(int x) {
        int digit_count = 0;
        int tmp = x;
        while (tmp != 0) {
            digit_count++;
            tmp /= 10;
        }
        return digit_count;
    }
    bool isPalindrome(int x) {
        if (x < 0)
            return false;
        //int dig_cnt = count(x);
        //x = abs(x);
        int divisor = 1, tmp = x;
        while (tmp/10 != 0) {
            divisor *= 10;
            tmp = tmp/10;
        }
        
        while (x != 0) {
            int last_dig = x/divisor;
            int first_dig = x % 10;
            if (last_dig != first_dig)
                return false;
            x = (x % divisor)/10;
            divisor /= 100;
        }
        return true;
    }
};

Longest Common Prefix

Problem:
Write a function to find the longest common prefix string amongst an array of strings.

Solution:
class Solution {
public:
    string findPrefix(string a, string b) {
        int size_a = a.size(), size_b = b.size();
        int size = min(size_a, size_b);
        int commonPrefix = 0;
        string sol;
        
        for (int i = 0; i < size; i++) {
            if (a[i] == b[i])
                commonPrefix++;
            else
                break;
        }
        return a.substr(0, commonPrefix);
    }
    string longestCommonPrefix(vector<string>& strs) {
        int size = strs.size();
        
        if (size == 0)
            return "";
        else if (size == 1)
            return strs[0];
        else if (size == 2)
            return findPrefix(strs[0], strs[1]);
        else {
            // Recursive approach
            /*
            vector<string> first, second;
            string firstHalf, secondHalf;
            for (int i = 0; i < size; i++) {
                if ((i % 2) == 0)
                    first.push_back(strs[i]);
                else
                    second.push_back(strs[i]);
            }
            firstHalf = longestCommonPrefix(first);
            secondHalf = longestCommonPrefix(second);
            return findPrefix(firstHalf, secondHalf);
           */
            
            // Iterative approach
            string sol = strs[0];
            for (int i  = 0; i < size; i++) {
                sol = findPrefix(strs[i], sol);
            }
            return sol;
        } 
    }
};

==== Optimized solution ====
// Check vertical 

class Solution {

public:

    string longestCommonPrefix(vector<string> &strs) {

        if (strs.empty()){return "";}

        if (strs.size()==1){return strs[0];}

         

        for (int i=0;i<strs[0].size();i++){

            for (int j=0;j<strs.size()-1;j++){

                if (i>=strs[j+1].size() || strs[j][i]!=strs[j+1][i]){

                    return strs[j].substr(0,i);

                }

            }

        }

         

        return strs[0];

    }

};

Valid Paranthesis

Problem:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Solution:
class Solution {
public:
    bool isValid(string s) {
        stack<char> tmp;
        int size = s.size();
        
        for (int i = 0; i < size; i++) {
            if (s[i] == '(' || s[i] == '{' || s[i] == '[')
                tmp.push(s[i]);
            else if (s[i] == ')') {
                if (tmp.empty() || tmp.top() != '(')
                    return false;
                tmp.pop();
            } else if (s[i] == '}') {
                if (tmp.empty() || tmp.top() !=  '{')
                    return false;
                tmp.pop();
            } else if (s[i] == ']') {
                if (tmp.empty() || tmp.top() !=  '[')
                    return false;
                tmp.pop();
            }
        }
        // Assuming empty string returns true;
        if (tmp.empty())
            return true;
        return false;
    }
};