Length of the longest substring

See the Pen Length of the longest substring by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

String to Leet

See the Pen String to Leet by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

Lessons Learnt:

mapper = {'a': 0};

if(mapper['a']) ---> is false

0 || undefined ---> is undefined

undefined || 0 ---> is 0

First Character Appearing Once

Problem

No. 13 - First Character Appearing Only Once
Implement a function to find the first character in a string which only appears once.
For example: It returns ‘b’ when the input is “abaccdeff”.

Solution Least Time

 Character getFirstUnique(char[] w)
 {
  HashMap m = new LinkedHashMap();
  for(int i=0; i< w.length; i++)
  {
   Integer cnt = m.get(w[i]);
   if(cnt == null) m.put(w[i], 1);
   else m.put(w[i], cnt+1);
  }
  
  for(int i=0; i< w.length; i++)
  {
   if(m.get(w[i]) == 1) return w[i];
  }

  return null;
 }

Solution Least Space

 public Character solnNoMem(char[] w)
 {
  for(int i=0; i< w.length; i++)
  {
   int cnt = 0;
   for(int j=0; j< w.length; j++)
   {
    if(i!=j && w[i] == w[j]) {
     cnt =1; break;
    }
   }
   if(cnt==0) return w[i];
  }
  return null;
 }

String compression

Problem

Implement a method to perform basic string compression using the counts
of repeated characters. For example, the string aabcccccaaa would become
a2blc5a3. If the "compressed" string would not become smaller than the original
string, your method should return the original string.

Note; this if from cracking the coding interview book

Solution

 public String compress(String s)
 {
  if(s.length()==0) return s;

  StringBuffer temp = new StringBuffer();
  Character lastChar = null;
  char currentChar = s.charAt(0);
  int count =1;
  for(int i=1; i< s.length(); i++)
  {
   if(s.charAt(i)==currentChar)
   {
    count++;
   }
   else 
   {
    temp.append(currentChar);
    temp.append(count);
    lastChar = currentChar;
    count = 1;
    currentChar = s.charAt(i);
   }
   System.out.println(temp.toString());
  }
  if(lastChar != currentChar) 
  {
   temp.append(currentChar);
   temp.append(count);
  }
  System.out.println(temp.toString());

  if(temp.length() < s.length())  return temp.toString();
  return s;
 }

Strings are permutations?

Problem

Find out if 2 strings are permutations of each other.

Solution

 private HashMap convertStringToMap(String s)
 {
  HashMap map = new HashMap();
  Integer mapValue;
  Character c;
  for(int i=0; i< s.length(); i++)
  {
   c = s.charAt(i);
   mapValue = map.get(c);
   if(mapValue == null) map.put(c, 1);
   else map.put(c, mapValue+1);
  }
  return map;
 }

 private boolean permutation(String string1, String string2) {

  if(string1.length() != string2.length()) return false;

  HashMap map1 = convertStringToMap(string1);
  HashMap map2 = convertStringToMap(string2);

  return map1.equals(map2);
 }

Build a simple regex function

Problem

Given a regular expression with characters a-z, ' * ', ' . '
the task was to find if that string could match another string with characters from: a-z
where ' * ' can delete the character before it, and ' . ' could match whatever character. ' * ' always appear after a a-z character.
Example:
isMatch("a*", "") = true;
isMatch(".", "") = false;
isMatch("ab*", "a") = true;
isMatch("a.", "ab") = true;
isMatch("a", "a") = true;

Solution

package myPackage;

public class Regex {

 boolean match(String r, String in)
 {
  int j= 0;
  for(int i= 0; i< r.length(); i++)
  {
   if(j >= in.length()) return false;
   if(r.charAt(i) != '.' && r.charAt(i) != '+' 
     && r.charAt(i) != '*' 
     && r.charAt(i) != '?')
   {
    int k = i+1;
    if((k< r.length() && r.charAt(k) != '.' 
      && r.charAt(k) != '+' 
      && r.charAt(k) != '*' 
      && r.charAt(k) != '?') 
      || k == r.length())
    {
     if(j< in.length() 
      && in.charAt(j)==r.charAt(i)) 
      j++;
     else return false;
     i--;
    }
    else if(r.charAt(k) == '*') 
     while(j< in.length() 
      && r.charAt(i) == in.charAt(j))
     {j++;}
    else if(r.charAt(k) == '?') 
     if(r.charAt(i) == in.charAt(j)) 
     {j++;}
    else if(r.charAt(k) == '+') 
     if(r.charAt(i) == in.charAt(j)) 
     {j++;} 
     else return false;
    else if(r.charAt(k) == '.') {
      if(r.charAt(i) == in.charAt(j)) 
      {j++;} 
      else return false;
      while(j< in.length() 
          && (r.charAt(i) == in.charAt(j)))
      {j++;}
     }
    i++;
   }
   else {
    int k = i;
    if(r.charAt(k) == '*') 
     while(j< in.length())
     {j++;}
    else if(r.charAt(k) == '?') 
      if(j< in.length()) 
       j++;
    else if(r.charAt(k) == '+') 
    {
     if(j< in.length()) j++; 
     else return false;
    }
    else if(r.charAt(k) == '.') 
    {
     if(j< in.length()) j++; 
     else return false;
     while(j< in.length()){j++;}
    }
   }
  }
  if(j< in.length()) return false;
  return true;
 }


 public static void main(String[] args) {

  Regex ob = new Regex();
  System.out.println(ob.match("aab*d*c*a*b*aa*", "aabbbcbbbaa"));
 }

}

Rotated Strings

Problem

Assume you have a method isSubstring which checks if one word is a substring
of another. Given two strings, s1 and s2, write code to check Ifs2 is a rotation of s1
using only onecalltoisSubstring (e.g., "waterbottLe" is a rotation of "erbottLewat").

Note: this is from Cracking the Coding Interview

Solution

 public boolean isRotation(String s1, String s2){
  if(s1.length() != s2.length() || s2.length() == 0) return false;
  return isSubString(s1 + s1, s2);
 }

Leetcode - Longest Substring Without Repeating Characters

Problem

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.

Accepted Solution

public class Solution {
     public int lengthOfLongestSubstring(String s) {

  int len=0; int start=0, pos=0, curLen=0, i=0;
  HashMap map = new HashMap();
  for(; i< s.length(); i++) 
                {
   if(map.containsKey(s.charAt(i)))
   {
    pos = map.get(s.charAt(i));
    curLen = i-start;
    if(curLen > len) len = curLen;
    if(pos >= start) start=pos+1;
   } 
   map.put(s.charAt(i),i);   
  }
  if(i== s.length() && i> 0) 
                {
          curLen = i-start;
   if(curLen > len) len = curLen;
  }
  return len;
 }
}

Strings replace spaces

Problem

Write a method to replace all spaces in a string with '%20'. You may assume that the
string has sufficient space at the end of the string to hold the additional characters,
and that you are given the "true" length of the string. (Note: if implementing in Java,
please use a character array so that you can perform this operation in place.)

Note: This is a problem from Cracking the Coding Interview Edition 5 Book.
Interesting part here: using Arrays.copy function

Solution

 private String replaceSpaces1(char[] s)
 {
  int count=0, i;
  int oldlen = s.length;

  for(i=0; i< oldlen; i++)
  {
   if(s[i] == ' ') count++;
  }


  int newlen = oldlen + count*2;
  s =  Arrays.copyOf(s, newlen);
  int pos = newlen-1;

  for(i= oldlen-1; i>= 0; i--)
  {
   if(s[i]==' ')
   {
    s[pos--] = '0';
    s[pos--] = '2';
    s[pos--] = '%';
   }
   else s[pos--] = s[i];
  }
  return Arrays.toString(s);
 }

Codility - Correct an incorrect License Key

Problem

Dashes have been inserted at the wrong places to generate an incorrect license key s. You need to correct the string such that a dash will be inserted after every k characters and make the string uppercase with complexity O(n). int k, and String s have been provided as inputs. You need to return the corrected license key

Solution

String solution(String a, int k)
 {
  StringBuffer res = new StringBuffer();
  int i, counter=0;
  for(i=0; i< a.length(); i++)
  {
   if(a.charAt(i) != '-') 
   {
    counter++;
    if((counter%k) == 1 && res.length() > 0) 
     {
      res.append("-");
      counter = 1;
     }
    res.append(Character.toUpperCase(a.charAt(i)));
   }
  }
  
  return res.toString();
 }

String has unique characters?

Problem Statement

Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

Solution 1 - With additional data structures

 public boolean uniqueString1(String s)
 {
  HashMap map = new HashMap();
  for(int i=0; i< s.length(); i++)
  {
   if(map.get(s.charAt(i))== null)
   {
    map.put(s.charAt(i), true);
   }
   else return false;
  }
  return true;
 }

Solution 2 - Without additional data structures

 public boolean uniqueString2(String s)
 {
  if(s.length() > 256) return false;

  int checker=0, val;
  for(int i =0;i < s.length();i++)
  {
   val = s.charAt(i) - 'a';
   if((checker & (1 << val)) > 0) return false;
   checker |= (1 << val);
  }
  return true;
 }

Note: This is a problem from the book "Cracking the Coding Interview: 150 Programming Questions and Solutions", which I am currently reading.

Generating Random Strings

How would you generate a random list of strings in java?

This is an exercise I set for myself today. And here's the code:

Collection generateRandomStrings(int numberOfStrings)
	{
		Random r = new Random();
		int range = 26, len;
		Character alphabet;
		StringBuffer word;
		
		List wordList = new ArrayList();
		for(int i=0; i< numberOfStrings; i++)
		{
			len = r.nextInt(5) +1;
			word = new StringBuffer();
			for(int j=0; j< len; j++)
			{
				alphabet = (char) ('a' + r.nextInt(range));
				word.append(alphabet);
			}
			wordList.add(word.toString());
		}
		return wordList;
	}