Valid Parentheses

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

 

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

Input: s = "{[]}"
Output: true

 

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

Solution

public static boolean isValidOrNot(String s) {
		boolean isValid = true;
		if (s.length() % 2 == 1) {
			isValid = false;
		} else {
			Stack<Character> stack = new Stack<Character>();
			for (char c : s.toCharArray()) {
				if (c == '(') {
					stack.add(')');
				} else if (c == '[') {
					stack.add(']');
				} else if (c == '{') {
					stack.add('}');
				} else {
					if (!stack.isEmpty() && c == stack.peek()) {
						stack.pop();
					} else {
						isValid = false;
						break;
					}
				}
			}
			if (!stack.isEmpty()) {
				isValid = false;
			}
		}
		System.out.println(isValid);
		return isValid;
	}

The above solution took 1ms for most of the cases, so tried to optimise to make it faster. Just for fun tried in leetcode, It took 0ms :)

 

public static void main(String[] args) {
		String s = "((";
		boolean isValid = true;
		if (s.length() % 2 == 1) {
			isValid = false;
		} else {
			int[] chatArray = new int[s.length()];
			int i = 0;

			for (char c : s.toCharArray()) {
				if (c == '(') {
					chatArray[i++] = ')';
				} else if (c == '[') {
					chatArray[i++] = ']';
				} else if (c == '{') {
					chatArray[i++] = '}';
				} else {
					if (i != 0 && c == chatArray[i - 1]) {
						i--;
					} else {
						isValid = false;
						break;
					}
				}
			}
			if (i != 0) {
				isValid = false;
			}
		}
		System.out.println(isValid);
	}

Thanks for reading :) 

Whether this post is helpful?

Have something to add to this post? If you have any other quick thoughts/hints that you think people will find useful? Share it in the comments. feedback are welcome...

Substring with Concatenation of All Words

 You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

 

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]

 

Constraints:

• 1 <= s.length <= 104
• s consists of lower-case English letters.
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] consists of lower-case English letters.

Solution:

public static List<Integer> findSubstring(String s, String[] words) {

		HashMap<String, Integer> hashMap = new HashMap<String, Integer>();

		ArrayList<Integer> index = new ArrayList<Integer>();

		int wordSize = words[0].length();

		int totalNoOfWords = words.length;

		int sizeOfWords = wordSize * totalNoOfWords;

		int n = s.length();

		if (sizeOfWords > n) {
			return index;
		}

		for (String word : words) {
			hashMap.put(word, hashMap.getOrDefault(word, 0) + 1);
		}

		for (int i = 0; i <= n - sizeOfWords; i++) {
			HashMap<String, Integer> tempMap = new HashMap<String, Integer>(hashMap);
			int j = i;
			int count = totalNoOfWords;

			while (j < i + sizeOfWords) {

				String word = s.substring(j, j + wordSize);

				if (!hashMap.containsKey(word) || tempMap.get(word) == 0) {
					break;
				} else {
					tempMap.put(word, tempMap.get(word) - 1);
					count--;
				}
				j = j + wordSize;
			}

			if (count == 0) {
				index.add(i);
			}

		}
		return index;
	}

	public static void main(String[] args) {
		String s = "wordgoodgoodgoodbestword";
		String[] words = new String[] { "word", "good", "best", "good" };

//		s = "barfoofoobarthefoobarman";
//		words = new String[] { "bar", "foo", "the" };

//		s = "barfoothefoobarman";
//		words = new String[] { "foo", "bar" };

		findSubstring(s, words);
	}

Thanks for reading :) 

Whether this post is helpful?

Have something to add to this post? If you have any other quick thoughts/hints that you think people will find useful? Share it in the comments. feedback are welcome...

Median of Two Sorted Arrays

 Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Follow up: The overall run time complexity should be O(log (m+n)).

 

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]
Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = []
Output: 2.00000

 

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

Solution:

public class MedianOfSortedArraysSolution {

	public static void main(String[] args) {

		int ar1[] = { 1, 2 }; // { 2, 3, 5, 8, 23 }; // { -5, 3, 6, 12, 15 };
		int ar2[] = { 3, 4 }; // { 10, 12, 14, 16, 18, 20 }; // { -12, -10, -6, -3, 4, 10 };

		int ar3[] = mergeSortedArrays(ar1, ar2);

		if (ar3.length % 2 == 1) {
			System.out.print((double) ar3[ar3.length / 2]);
		} else {
			System.out.print((double) (ar3[(ar3.length - 1) / 2] + ar3[(ar3.length + 1) / 2]) / 2);
		}
	}

	private static int[] mergeSortedArrays(int[] ar1, int[] ar2) {

		int n = 0;
		int m = 0;
		int l = 0;
		int ar3[] = new int[ar1.length + ar2.length];

		while (n < ar1.length || m < ar2.length) {

			if (n == ar1.length || (m != ar2.length && ar1[n] > ar2[m])) {
				ar3[l] = ar2[m];
				m++;
			} else {
				ar3[l] = ar1[n];
				n++;
			}
			l++;
		}

		return ar3;
	}

}

Thanks for reading :) 

Whether this post is helpful?

Have something to add to this post? If you have any other quick thoughts/hints that you think people will find useful? Share it in the comments. feedback are welcome...

Longest Substring Without Repeating Characters

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

Example 1:

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

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = ""
Output: 0

 

Solution:

Before jumping to solve the problem, Give few mins gap and think. How can you approach for the problem...

Steps:

1. Add every character to set (Ex: i = 0 ; j = 0)

2. Check if the character is existing in the set or not ( increment i and add the char to set)

3. If it exist then take the max size of set and clear the set and start from the next character again.

(if char exist then get max value of set and increment j and assign j to i and loop again)

import java.util.HashSet;

public class LongestSubstringWithoutRepeatChar {

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcabcd"));
    }

    public static int lengthOfLongestSubstring(String s) {

        HashSet<Character> store = new HashSet<Character>();
        int max = 0;
        for (int i = 0, j = 0; i < s.length();) {
            if (!store.contains(s.charAt(i))) {
                store.add(s.charAt(i));
                i++;
            } else {
                i = j++;
                max = Math.max(max, store.size());
                store.clear();
            }
        }
        max = Math.max(max, store.size());
        return max;
    }
}

Thanks for reading :) 

Whether this post is helpful?

Have something to add to this post? If you have any other quick thoughts/hints that you think people will find useful? Share it in the comments. feedback are welcome...

Longest Word in Dictionary through Deleting (Find largest subsequence word from Dictionary)

Problem statement:

Longest Word in Dictionary through Deleting 

Find largest subsequence word from the given dictionary

Both the above problem statement is same.

Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:

Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output: 
"apple"

Example 2:

Input:
s = "abpcplea", d = ["a","b","c"]

Output: 
"a"

Note:

1. All the strings in the input will only contain lower-case letters.
2. The size of the dictionary won't exceed 1,000.
3. The length of all the strings in the input won't exceed 1,000.

Solution

Before jumping to solve the problem, Give few mins gap and think. How can you approach for the problem...

Steps:

1. We need to have 2 for loops. One is to fetch word from dictionary and other for loop is iterate the word and check.

2. Write a logic to identify the largest subsequence of the word.

3. If we find more than 1 largest subsequence we need to return the smallest lexicographical order one.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LongestWordSolution {
		
	public static void main(String[] args) {

		System.out.println(findLongestWord("bab", new String[] { "ba", "ab", "cad" }));
	}

	public static String findLongestWord(String s, String[] d) {
	
		if (s == null || d == null || s.isEmpty()) {
			return "";
		}

		String result = "";
		int max = 0;
		for (String str : d) {
			int count = 0;
			for (int i = 0, j = 0; i < str.length() && j < s.length();) {
				if (str.charAt(i) == s.charAt(j)) {
					i++;
					j++;
					count++;
				} else {
					j++;
				}
			}
			if (count == str.length()) {
				if (count == max) {
					if (result.compareTo(str) > 0) {
						result = str;
					}
				} else {
					max = Math.max(max, count);
					if (count == max) {
						result = str;
					}
				}
			}
		}

		return result;
	}
}

Time Complexity - O(MN) - M is the length of dictionary and N is the length of the string

Space Complexity - O(1)

Thanks for reading :) 

Whether this post is helpful?

Have something to add to this post? If you have any other quick thoughts/hints that you think people will find useful? Share it in the comments. feedback are welcome...