Tag: java
-
Data Structures & Algorithms in Java – Strings – Longest Palindromic Substring
Problem: Given a string , find the longest palindromic substring in that string. For example , for the input “babad” the longest palindromic substring is “bab” or “aba”. For the input “cbbd” the longest palindromic substring is “bb” Assumptions: The string has at least one character and at the most 1000 characters The string consists…
-
Data Structures & Algorithms in Java – Strings – Valid Palindrome
Problem: Given a string with both alphanumeric and non alphanumeric characters , find if it is a valid palindrome ignoring the non alphanumeric characters and converting the upper case letters to lower case letters For example, The input: “A man , a plan, a canal: Panama” is a valid palindrome after you remove the special…
-
Data Structures & Algorithms in Java – Strings – Valid Parantheses
Problem: Given a string containing parantheses ( (,).{,},[,]) check if the parantheses match or not. For example, The string “()[]{}” is a valid string because the opening parentheses are matched by closing ones. The string “{[()]}” is also a valid expression since all the opening parentheses have corresponding closing parentheses The string “(]” is invalid…
-
Data Structures & Algorithms in Java – Strings – Group Anagrams
Problem: Given a list of words , group anagrams together and create a list of anagram lists. Example: For the input : [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”] The output is : [ [“eat”,”tea”,”ate”],[“tan”,”nat”],[“bat”]] Assumptions: the letters are in lowercase English the order of the words in the anagram list doesn’t matter Try out the solution here: https://leetcode.com/problems/group-anagrams/ Solution: Hint:…
-
Data Structures & Algorithms in Java – Strings – Minimum Window Substring
Problem: Given two strings s and t , find the minimum window substring from s which contains all the characters of the string t. For example, For the input strings s = “ADOBECODEBANC” t = “ABC” The minimum window substring in s is “BANC” The possible substrings are “ADOBEC” , “BECODEBA” , “CODEBA” and “BANC”…
-
Data Structures & Algorithms in Java – Strings – Longest Repeating Character Replacement
Problem: Given a string and a number k find the longest substring whose characters can be replaced by the most repeating character to a maximum of k times. Example: Given string = “ABAB” and k = 2 You can replace the substring “ABAB” with “BBBB” since the two A’s are not the most repeating character…
-
Data Structures & Algorithms in Java – String – Longest Substring Without Repeating Characters
Problem: Given a string , find the longest substring in the string without any repeating characters. Example: For the input abcabcbb , the longest substring is abc , so the output is 3 For the input dvdf , the longest substring is vdf , so the output is 3 Try out the solution here: https://leetcode.com/problems/longest-substring-without-repeating-characters…
-
Data Structures & Algorithms in Java – Dynamic Programming – Unique Paths
Problem: Given a 2 dimensional matrix size m * n , find the number of unique ways to reach the bottom right of the matrix from the top left of the matrix (first cell) if you can move only right or down a step at a time . That is from input[0][0] to input[m-1][n-1] For…
-
Data Structures & Algorithms in Java – Dynamic Programming – Decode Ways
Problem: If A is encoded as 1 , B as 2 and so on until Z as 26 , then find the number of ways a given encoded string can be decoded. For example: The input “121” can be decoded as 1, 2 ,1 (ABA) or 12 1(LA) or 1 21 (AU) So the output…
-
Data Structures and Algorithms in Java – Dynamic Programming – Combination Sum
Problem: Given an array of numbers and a target number , find in how many ways the numbers in the input array can be summed up to form the target number. For example, Given the input: [1,2,3] and the target 4 The output should be 7 since : 1 + 1 + 1 + 1…