Longest Substring Without Repeating Characters

Problem Statement
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.

Source: https://leetcode.com/problems/longest-substring-without-repeating-characters/
Programming Language: C#
Run Time Complexity: O(n)
Space Complexity: O(n)

Solution

public int LengthOfLongestSubstring(string s)
{
    if ((s == null) || (s.Length <= 0))
        return 0;    
    else if (s.Length == 1)
        return 1;

    // Dictionary to keep track of character and index position
    Dictionary<char, int> dictionary = new Dictionary<char, int>();
    int count = 0;
    int max_count = Int32.MinValue;
    int start_marker = 0;
    int end_marker = 0;
    

    while ((start_marker < s.Length) && (end_marker < s.Length))
    {
        if (!dictionary.ContainsKey(s[end_marker]))
        {
            dictionary.Add(s[end_marker], end_marker);
        }
        else if (dictionary.ContainsKey(s[end_marker]))
        {
            // Check if the index is in between start and end marker
            if ((dictionary[s[end_marker]] >= start_marker) && (dictionary[s[end_marker]] <= end_marker))
            {
                //update the count
                count = end_marker - start_marker;

                // update the max count
                max_count = Math.Max(count, max_count);

                // set the position of start marker
                start_marker = dictionary[s[end_marker]] + 1;
            }
            // Update with the current index
            dictionary[s[end_marker]] = end_marker;
        }
        end_marker++;
    }

    // for the end condition
    max_count = Math.Max(end_marker - start_marker, max_count);

    return max_count;
}

Two Sum

Problem Statement

 

Given an array of integers, find two numbers such that they add up to a specific target number.

 

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

 

Please note that your returned answers (both index1 and index2) are not zero-based.

 

You may assume that each input would have exactly one solution. Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

 

Source: https://leetcode.com/problems/two-sum/
Programming Language: C#
Run Time Complexity: O(N)
Space Complexity: O(N)

Solution 
 

public Tuple<int, int> TwoSum(int[] numbers, int target)
{
    // Maintain map for the integers to have O(1) lookup
    Dictionary<int, int> dictionary = new Dictionary<int, int>();
            
    for (int index = 0; index < numbers.Length; index++)
    {
        // If exists in the map
        if (dictionary.ContainsKey(target - numbers[index]))
        {
            // Output is expected ordered by index
            if (index < dictionary[target - numbers[index]])
                return new Tuple<int, int>(index + 1, dictionary[target - numbers[index]] + 1);
            else
                return new Tuple<int, int>(dictionary[target - numbers[index]] + 1, index + 1);
        }
        else
        {
            if (!dictionary.ContainsKey(numbers[index]))
                dictionary.Add(numbers[index], index);
        }
    }

    // Return null if solution not found
    return null;
}