Posts

Find the longest substring without repeating characters

Sliding Window is a subarray running on a large array, which is a collection of underlying elements. Here we use two pointers, one pointer A always selects the first char of the max substring, from each iteration of the string. The second pointer B runs ahead of pointer A, until a duplicate character is found or the end of the string is reached. public int lengthOfLongestSubstring(String s) { int a_pointer = 0; int b_pointer = 0; int max = 0; Set<Character> hashSet = new HashSet<>(); int i = 0; while(b_pointer < s.length()) { if(!hashSet.contains(s.charAt(b_pointer))) { hashSet.add(s.charAt(b_pointer)); b_pointer++; max = Math.max(hashSet.size(), max); } else { hashSet.remove(s.charAt(a_pointer)); a_pointer++; } } return max; }
Post a Comment
Read more

Find all the permutations of a string - similar to permute arrays

Image
Recursive Solution Example String: abcdefgh When i = 0, we have, First wave of recursion till the String is empty Input String: abcdefgh - ""  +  "bcdefgh" = "bcdefgh" Input String: bcdefgh - ""  +  "cdefgh"    = "cdefgh" Input String: cdefgh - ""  +  "defgh"       = "defgh" Input String: defgh - ""  +  "efgh"           = "efgh" Input String: efgh - ""  +  "fgh"               = "fgh" Input String: fgh - ""  +  "gh"                  = "gh" Input String: gh - ""  +  "h"                     = "h" Input String: h - ""  +  ""                         = "" Then coming out of recursion Input String: gh - "g"  +  "" = "g" Input String: g - ""...
Post a Comment
Read more

Find the maximum occurring character in given String ?

public static void main(String[] args) { System.out.println(maxOccurringChar("122333444455555666666")); } public static Character maxOccurringChar(String s) { Map<Character, Integer> charCountMap = new HashMap<>(); char[] array = s.toCharArray(); for (int i = 0; i < array.length; i++) { if(array[i] != ' ') { Integer occ = charCountMap.getOrDefault(array[i], 0); charCountMap.put(array[i], ++occ); } } Map.Entry<Character, Integer> maxEntry = charCountMap.entrySet().stream() .max(Map.Entry.comparingByValue()).get(); // Map.Entry<Character, Integer> maxEntry = getEntryWithMaxValue(charCountMap); System.out.println(String.format("Character %s occurs %s times.", maxEntry.ge...
Post a Comment
Read more

Find if the String is a number or floating point number - Regular Expression

Find if a string contains only digits? public static boolean stringContainsOnlyDigits(String s) { Pattern p = Pattern.compile( "^[0-9]+$" ); Matcher m = p.matcher( s ); return m.find(); } Find if the String is a Floating Point number. public static boolean stringIsFloatingPointNumber(String s) { Pattern p = Pattern.compile( "^[-+]?[0-9]*\\.?[0-9]+$" ); Matcher m = p.matcher( s ); boolean found = m.find(); if(found) { System.out.println("found: " + m.group(0)); } return found; } The caveat here is the strings are long text and Double.parseDouble() will be out of range. Such problems can be solved only using Regular Expressions .
Post a Comment
Read more

Print staircase with both base and height equal to n

Consider a staircase of size n=4, as shown below:       #     ##   ### #### Observe that its base and height are both equal to n, and the image is drawn using # symbols and spaces. The last line is not preceded by any spaces. Write a program that prints a staircase of size n. public static void main(String[] args) { int n = 10; if(n < 1 || n > 100) { throw new IllegalArgumentException("N should be between 0 and 100"); } for (int i = 1; i <= n; i++) { System.out.println(Stream.concat(Stream.generate(() -> " ").limit(n-i), Stream.generate(() -> "#").limit(i)) .collect(Collectors.joining())); } } }
Post a Comment
Read more

Given an n x n square matrix, find sum of all sub-squares of size k x k

Solution: for (int i = 0; i < n-k+1; i++) { for (int j = 0; j < n-k+1; j++) { int sum = 0; for (int p = i; p < k+i; p++) for (int q = j; q < k+j; q++) sum += mat[p][q]; } }
Post a Comment
Read more