Leetcode 3. Longest Substring Without Repeating Characters

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

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequenceand not a substring.

Solution in C

int is_present (char ch, char *sol, int front, int rear, int size) {
    int i;
   
    if (front == 0 && rear == -1)
        return -2;

    for (i = rear; (i != front); i = (i + 1) % size) {
        if (sol[i] == ch)
            return i;
    }
    /*
    if (rear == front - 1) {
        if (sol[i] == ch)
            return i;
    }*/
       
    return -1;
}

int lengthOfLongestSubstring(char* s) {
    char *sol;
    int len, front = 0, rear = -1, i = 0;
    int curr_len = 0, max_len = 0, size, op;
   
    len = strlen(s);
   
    if (len == 0)
        return 0;
   
    size = len + 1;
    sol = (char *)malloc(sizeof(char) * size);
   
    if (sol == NULL)
        return 0;
       
    while (i < len) {
        op = is_present(s[i], sol, front, rear, size);
        switch (op) {
            case -2:
                sol[front] = s[i];
                front++;
                rear = 0;
                curr_len = front - rear;
                max_len = curr_len;
                break;
           
            case -1:
                sol[front] = s[i];
                front = (front + 1) % size;
                curr_len++;
                if (max_len < curr_len)
                    max_len = curr_len;
                break;
            default:
                sol[front] = s[i];
                rear = (op + 1) % size;
               
                /*if (rear == front)
                    rear = front;
                 */ 
                front = (front + 1) % size;
               
                if (front >= rear) {
                    curr_len = front - rear;
                } else {
                    curr_len = (size - rear) + front;
                }
                if (max_len < curr_len)
                    max_len = curr_len;
                break;
           
        }
        i++;
    }
    free(sol);
    return max_len;
   
}

Solution in Python:

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        max_len = 0
        i = 0
       
        while i < len(s):
            dic = {}
            dic[s[i]] = 1
            j = i + 1
            count = 1
            while j < len(s):
                if s[j] in dic:
                    break
                count = count + 1
                dic[s[j]] = 1
                j = j + 1
            if count > max_len:
                max_len = count
            i = i + 1
           
        return max_len

Leetcode Problem 2. Add Two Numbers

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 contain a single digit. Add the two numbers and return it as a linked list.

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

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Explanation: 342 + 465 = 807.

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     struct ListNode *next;

 * };

 */

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {

    struct ListNode *l3 = NULL, *t1, *t2, *t3;

    int carry = 0, sum = 0;

    

    t1 = l1;

    t2 = l2;

    

    while (t1 != NULL && t2 != NULL) {

        if (l3 == NULL) {

            l3 = (struct ListNode *)malloc(sizeof(struct ListNode));

            if (l3 == NULL)

                return NULL;

            l3->next = NULL;

            t3 = l3;    

        } else {

            t3->next = (struct ListNode *)malloc(sizeof(struct ListNode));

            if (t3->next == NULL)

                return NULL;

                

            t3 = t3->next;

            t3->next = NULL;

        }

        sum = t1->val + t2->val + carry;

        carry = 0;

        if (sum >= 10) {

            carry = 1;

            sum -= 10;

        }

        t3->val = sum;

        

        t1 = t1->next;

        t2 = t2->next;

    }

    while  (t1 != NULL) {

        t3->next = (struct ListNode *)malloc(sizeof(struct ListNode));

            if (t3->next == NULL)

                return NULL;

                

            t3 = t3->next;

            t3->next = NULL;

            sum = t1->val + carry;

            carry = 0;

            if (sum >= 10) {

                carry = 1;

                sum -= 10;

            }

            t3->val = sum ;

            t1 = t1->next;

    }

    

    while  (t2 != NULL) {

        t3->next = (struct ListNode *)malloc(sizeof(struct ListNode));

            if (t3->next == NULL)

                return NULL;

                

            t3 = t3->next;

            t3->next = NULL;

            sum = t2->val + carry;

            carry = 0;

            if (sum >= 10) {

                carry = 1;

                sum -= 10;

            }

            

            t3->val = sum;

            t2 = t2->next;

    }

    

   if (carry == 1) {

        t3->next = (struct ListNode *)malloc(sizeof(struct ListNode));

        if (t3->next == NULL)

            return NULL;

            

        t3 = t3->next;

        t3->next = NULL;

            

        t3->val = carry;    

    }

    return l3;

}

Solution in Python:

# Definition for singly-linked list.

#class ListNode(object):

#    def __init__(self, x):

#        self.val = x

#self.next = None

class Solution(object):

    def reverseList(self, l1):

        prev = None

        curr = l1

        next = None

        while (curr != None):

            next = curr.next

            curr.next = prev

            prev = curr

            curr = next

            

        return prev

    

    def printList(self, l1):

        while(l1 != None):

            print(l1.val)

            print(",")

            l1 = l1.next

        

    def addTwoNumbers(self, l1, l2):

        """

        :type l1: ListNode

        :type l2: ListNode

        :rtype: ListNode

       """

        

        carry = 0

        l3 = None

        head = None

        while ((l1 != None) and (l2 != None)):

            s = l1.val + l2.val + carry

            print(str(s))

            carry = 0

            if (s > 9) :

                carry = 1

                s = s % 10

            if (head == None):

                l3 = ListNode(s)

                head = l3

                l1 = l1.next

                l2 = l2.next

                continue

            l3.next = ListNode(s)

            l3 = l3.next

            l1 = l1.next

            l2 = l2.next

        

        

        while (l1 != None):

            s = l1.val + carry

            carry = 0

            if (s > 9):

                carry = 1

                s = s % 10

            tmp = ListNode(s)

            if (head == None):

                l3 = tmp

                head = l3

                l1 = l1.next

                continue

            l3.next = tmp

            l3 = tmp

            l1 = l1.next

            

        while (l2 != None):

            s = l2.val + carry

            carry = 0

            if (s > 9):

                carry = 1

                s = s % 10

            tmp = ListNode(s)

            if (head == None):

                l3 = tmp

                head = l3

                l2 = l2.next

                continue

            l3.next = tmp

            l3 = tmp

            l2 = l2.next

            

        if (carry != 0):

            tmp = ListNode(carry)

            l3.next = tmp

            

            

        return head

Leetcode Problem 1 - Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1]

Solution in C

Suppose a+b = target 

                a = target - b

     

insert target - b in map and while lookup if we find a then we got a pair.

The idea is to create a map in C.  

typedef struct map_ {
    int num;
    int index;
    struct map_ *next;
}map_t;

#define MAX_KEY     1000
map_t *table[MAX_KEY] , *neg_table[MAX_KEY];

map_t *alloc_map() {
    map_t *elem = (map_t *)calloc(1, sizeof(map_t));
    return elem;
}

void init_map() {
    int i;
   
    for(i = 0; i < MAX_KEY; i++) {
        table[i] = NULL;
        neg_table[i] = NULL;
    }
}

void insert_pos_elem(int num, int index) {
    int key = 0;
    
    key = num % MAX_KEY;
    map_t *head = table[key], *tmp;
    
    if (head == NULL) {
        table[key] = alloc_map();
        table[key]->num = num;
        table[key]->index = index;
    } else {
        tmp = alloc_map();
        tmp->num = num;
        tmp->index = index;
        tmp->next = head;
        
        table[key] = tmp;
    }
}

void insert_neg_elem(int num, int index) {
    int key = 0;
    
    key = num % MAX_KEY;
    map_t *head = neg_table[key], *tmp;
    
    if (head == NULL) {
        neg_table[key] = alloc_map();
        neg_table[key]->num = num;
        neg_table[key]->index = index;
    } else {
        tmp = alloc_map();
        tmp->num = num;
        tmp->index = index;
        tmp->next = head;
        
        neg_table[key] = tmp;
    }
}

void insert_elem(int num, int index) {
    if (num < 0) {
        num = 0 - num;
        insert_neg_elem(num, index);
    } else {
        insert_pos_elem(num, index);
    }
}


map_t *lookup_elem(int num) {
    int key = 0;
    map_t *head = table[key];
    
   if (num < 0) {
        num = 0 - num;
        key = num % MAX_KEY;
        head = neg_table[key];
   } else {
        key = num % MAX_KEY;
        head = table[key];
   }
    
    while(head != NULL) {
        if (head->num == num)
            return head;
        head = head->next;
    }
    return NULL;
}

int * twoSum(int* nums, int numsSize, int target) {
    int i, n1, *ret = NULL;
    map_t *elem = NULL;
    
    if (nums == NULL)
        return NULL;
    
    init_map();
    
    for (i = 0; i < numsSize; i++) {
        elem = lookup_elem(nums[i]);
        if (elem == NULL) {
            insert_elem((target - nums[i]), i);
        } else {
            n1 = elem->index;
            ret = (int *)calloc(2, sizeof(int));
            ret[0] = n1;
            ret[1] = i;
            return ret;
        }
    }
    
    return ret;
}

Solution in cpp

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        std::vector < int > v;
        std::map < int, int > m;
        std::vector < int >::iterator it;

        for (it = nums.begin(); it != nums.end(); it++) {
           
            m[target - *it] = it - nums.begin();
        }

        std::map < int, int >::iterator m_it;
        for (it = nums.begin(); it != nums.end(); it++) { 
            m_it = m.find(*it);
            if (m_it == m.end())
                continue;
            int index = it - nums.begin();
            if (index ==  m_it->second)
                continue;
            v.push_back(m_it->second);
            v.push_back(it - nums.begin());
            break;
        }
        return v; 
    }

};

Solution in python:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dic={}
        res=[]
        for i in range(len(nums)):
            dic[target - nums[i]]=i
        print (dic)
        for i in range(len(nums)):
            if nums[i] in dic:
                if i == dic[nums[i]]:
                    continue
                res.append(i)
                res.append(dic[nums[i]])
                break

        return res