Longest Common Prefix

Problem Statement

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

Source: https://leetcode.com/problems/longest-common-prefix/

Programming Language: C#
Run Time Complexity: if n is the length of shortest string in array of strings and there are m strings in the array. Run time complexity would be O(m*n)

Space Complexity: Constant space

Solution

public string LongestCommonPrefix(string[] strs)
{
    // Input Validation
    if ((strs == null) || (strs.Length <= 0))
        return "";

    // First string in the array of Strings
    string firstString = strs[0];

    // If the length of array of strings is 1 you can return the first string
    if (strs.Length == 1)
        return firstString;
    
    // For all characters in the first string
    for (int index = 0; index < firstString.Length; index++)
    {
        // Index for the string array
        for (int strsIndex = 1; strsIndex < strs.Length; strsIndex++)
        {
            // Condition 1: index should be less than the current string in the array
            // Condition 2: character at index should match with the character of the current string
            if ((index > strs[strsIndex].Length - 1) || (strs[strsIndex][index] != firstString[index]))
                return firstString.Substring(0, index);
        }
    }

    // If first string is ended that is the common prefix 
    return firstString;
}

Roman To Integer

Problem Statement

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999

Programming Language: C#
Run Time Complexity: O(N)
Space Complexity: Constant space
Resources: http://en.wikipedia.org/wiki/Roman_numerals
Source: https://leetcode.com/problems/roman-to-integer/
Solution

public int RomanToInt(string s)
{
    // Input validation
    if (string.IsNullOrEmpty(s))
        return 0;

    // 4:IV, 9:IX, 40:XL, 90:XC, 400:CD, 900:CM,
    // 1:I, 10:X, 100:C, 1000:M
    int output = 0;
    // Prev is previous character in the input string
    char pre = ' ';

    for (int i = 0; i < s.Length; i++)
    {
        if (s[i] == 'M' && pre != 'C') { output += 1000; }
        if (s[i] == 'C' && pre != 'X') { output += 100; }
        if (s[i] == 'X' && pre != 'I') { output += 10; }

        if (s[i] == 'M' && pre == 'C') { output += 800; }
        if (s[i] == 'C' && pre == 'X') { output += 80; }
        if (s[i] == 'X' && pre == 'I') { output += 8; }

        if (s[i] == 'I') { output += 1; }

        if (s[i] == 'V' && pre != 'I') { output += 5; }
        if (s[i] == 'L' && pre != 'X') { output += 50; }
        if (s[i] == 'D' && pre != 'C') { output += 500; }

        if (s[i] == 'V' && pre == 'I') { output += 3; }
        if (s[i] == 'L' && pre == 'X') { output += 30; }
        if (s[i] == 'D' && pre == 'C') { output += 300; }

        pre = s[i];

    }

    // Return output
    return output;
}

Integer to Roman

Problem Statement

Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.

Programming Language: C#
Run Time Complexity: O(N)
Space Complexity: Constant space
Resources: http://en.wikipedia.org/wiki/Roman_numerals
Source: https://leetcode.com/problems/integer-to-roman/

Solution

public string IntToRoman(int num)
{
    // Maintain a mapping of numbers to roman numerals staring from highest numeral
    int[] integer = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
    String[] roman = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
    
    // Output 
    string output = "";

    // Input validation (Num should be in the range of 1-3999)
    if (num <= 0)
        return output;

    for (int index = 0; index < integer.Length; index++)
    {
        int result = num / integer[index];

        // Append the roman numeral equal to the result 
        while (result > 0)
        {
            output += roman[index];
            result--;
        }

        // Continue the processing with the remainder
        num = num % integer[index];
    }

    // return output
    return output;
}

ZigZag Conversion

Problem Statement

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Source: https://leetcode.com/problems/zigzag-conversion/
Programming Language: C#
Run Time Complexity: O(n)
Space Complexity: O(n)

Solution:

public string Convert(String s, int nRows)
{
    string result = "";

    // Input Validation
    if ((s == null) || (s.Length == 0))
        return result;

    // Input Validation
    if (nRows <= 0)
        return "";

    // Input Validation
    if (nRows == 1)
        return s;

    // Create Array of strings
    string[] strstr = new string[nRows];
            
    // Index for Array of strings 
    int strstrIndex = 0;

    // Tracks direction down / up
    bool down = true;

    for (int index = 0; index < s.Length; index++)
    {

        strstr[strstrIndex] += s[index];

        if (down)
            strstrIndex++;
        else
            strstrIndex--;

        // If reached down completely
        if (strstrIndex == nRows)
        {
            strstrIndex -= 2;
            down = false;
        }

        // If reached up completely
        if (strstrIndex == -1)
        {
            strstrIndex += 2;
            down = true;
        }
    }

    // Append all the strings and return
    for (int index = 0; index < nRows; index++)
        result += strstr[index];

    return result;
}

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;
}