coderz.py

In the previous post, we got an introduction to Strings and their methods. Let us now take a look at a few problems related to it.

Given a string s, return the longest palindromic substring in s.

Example:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Solution:

class Solution {
    public String longestPalindrome(String s) {
        char[] charArray = s.toCharArray();
        int start = 0;
        int maxLen = 0;
        for (int i = 0; i < charArray.length; i++) {
            for (int len = 0; i + len < charArray.length; len++) {
                if (isPalindrome(charArray, i, len) && len + 1 > maxLen) {
                    maxLen = len + 1;
                    start = i;
                }
            }
        }

        return s.substring(start, start + maxLen);
    }

    public boolean isPalindrome(char[] charArray, int start, int len) {
        while (len > 0) {
            if (charArray[start] != charArray[start + len]) {
                return false;
            }

            start++;
            len -= 2;
        }

        return true;
    }
}

Time complexity: O(n^3), where n is the length of the input string

Space complexity: O(1)

• The given code contains two methods, one for finding the longest palindrome substring in a given string, and the other method isPalindrome() checks if a given substring is a palindrome or not.
• The approach of the longestPalindrome() method is to loop through all the possible substrings of the given string and check if each substring is a palindrome or not using the isPalindrome() method.
• If a palindrome substring is found whose length is greater than the previously found palindrome substring, then its length and starting index are updated.

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

Example:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Solution:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int left = 0, right = 0;
        int maxLength = 0;
        HashSet<Character> set = new HashSet<>();

        while (right < n) {
            if (!set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                right++;
                maxLength = Math.max(maxLength, right - left);
            } else {
                set.remove(s.charAt(left));
                left++;
            }
        }

        return maxLength;
    
    }
}

Time complexity: O(n), where n is the length of the input string

Space complexity: O(min(n, m)), where n is the length of the input string

• Here we used a sliding window approach with two pointers, left and right.
• We also use a HashSet to keep track of the characters in the current substring. Then start with left = 0 and right = 0.
• We then move the right pointer to the right until we encounter a character that is already in the HashSet. Now record the length of the current substring and shift the left pointer to the right until the duplicate character is removed from the HashSet.

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "".

Example:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Solution:

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }

        String prefix = strs[0];

        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }

        return prefix; 
    }
}

Time complexity: O(S), where S is the total number of characters in all strings combined

Space complexity: O(1)

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I                       1
V                      5
X                      10
L                       50
C                      100
D                      500
M                     1000

Given a roman numeral, convert it to an integer.

Example:

Input: s = "III"
Output: 3
Explanation: III = 3.

Solution:

class Solution {
    public int romanToInt(String s) {
         Map<Character, Integer> symbolToValue = new HashMap<>();
        symbolToValue.put('I', 1);
        symbolToValue.put('V', 5);
        symbolToValue.put('X', 10);
        symbolToValue.put('L', 50);
        symbolToValue.put('C', 100);
        symbolToValue.put('D', 500);
        symbolToValue.put('M', 1000);

        int total = 0;
        int prevValue = 0;

        for (int i = 0; i < s.length(); i++) {
            int curValue = symbolToValue.get(s.charAt(i));
            total += curValue;
            if (curValue > prevValue) {
                total -= 2 * prevValue;
            }
            prevValue = curValue;
        }

        return total;
    }
}

Time complexity: O(N), where N is the length of the input string

Space complexity: O(1)

we started by creating a HashMap to map each symbol to its corresponding value and iterated over the input string and add the value of each symbol to the total, subtracting the value of the previous symbol if it is less than the current symbol.

Given an integer, convert it to a Roman numeral.(Above question part -II)

Solution:

class Solution {
    public String intToRoman(int num) {
         int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                num -= values[i];
                sb.append(symbols[i]);
            }
        }

        return sb.toString();
    }
}

Time complexity: O(1)

Space complexity: O(1)

Again, we created a mapping from the integer values to their corresponding Roman numeral symbols. We then iterate over the mapping in descending order, subtracting the value of each symbol from the input integer until the input integer becomes 0.

Note: also read about DSA: Strings Concept

Follow Me

If you like my post please follow me to read my latest post on programming and technology.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py