Java Program to Check whether a Expression is Valid

Java Program to Check whether a Expression is Valid

// Using count variables for character and brackets

 public static boolean isValidStr(String str)
 {
  int count = 0, brackets = 0;
  for(int i = 0; i< str.length(); i++)
  {
   char ch = str.charAt(i);
   
   switch(ch)
   {
    case '+':
     count--; 
     break;
    case '-':
     count--; 
     break;
    case '*':
     count--; 
     break;
    case '/':
     count--; 
     break;
    case '(':
     brackets++; 
     break;
    case ')':
     brackets--; 
     break;
    default:
     count++; 
     break;
   }
   
   if(count > 1 || count < 0 || brackets < 0) return false;
   
  }
  
  if(brackets != 0) return false;
  
  if(count != 1) return false;
  
  return true;
  
 }
 

Print all permutation of given string in Java

Program:

Note: We can use Set data structure to avoid repeated elements.

Length of the longest substring without repeating characters in Java

Given a string, find the length of the longest substring without repeating characters. For example, the longest substrings without repeating characters for “ABDEFGABEF” are “BDEFGA” and “DEFGAB”, with length 6. For “BBBB” the longest substring is “B”, with length 1. For “GEEKSFORGEEKS”, there are two longest substrings shown in the below diagrams, with length 7.

Program:

Reference:
http://www.geeksforgeeks.org/length-of-the-longest-substring-without-repeating-characters/

Rearrange a string so that all same characters become d distance away

// Steps to rearrange the string:
// - define array with size 256 which contains frequency of char index.
// - define heap node with key of type char and its frequency of type int
// - create max heap as per frequency element heap node
// - Itreate till length of string
//    remove max frequency node from heap
//    place it at k = i + (f-1)*d positions of result string


static String rearrange(String str, int d) throws CustomException{
int n = str.length();
if(n == 0 || n == 1) return str;
char[] res = new char[n];
for(int i=0; i {
res[i] = 0;
}

int[] arrf = new int[260];

heapnd[] hn = new heapnd[n];

  for (int i = 0; i {
arrf[str.charAt(i)] ++;
}
  int j =0;
  for(int i = 0; i<260 i="" p="">  {
  if(arrf[i] != 0)
  {
  hn[j++] = new heapnd((char) i ,arrf[i]);
  }
  }
 
  maxHeap(hn,j);
 
  for(int i =0; i  {
  if(res[i] != 0)
  {
  continue;
  }
heapnd maxfreq = hn[0];
int k;
for(int l = 1; l<= maxfreq.freq; l++)
{
k = i + (l-1)*d;
if(k>n-1) throw new CustomException("Can't rearrange this string.");
res[k] = maxfreq.key;
}
if(j > 0)
{
hn[0] = hn[j-1];
j = j-1;
maxheapify(hn, 0, j);
}
  }
 
  return new String(res);
 
 
}

private static void maxHeap(heapnd[] hn, int n){
if(n == 0 || n == 1) return;

for(int i = (n-1)/2; i>=0; i--)
{
maxheapify(hn, i, n);
}
}


private static void maxheapify(heapnd[] hn, int i, int n) {

int l = left(i);
int r = right(i);
int maxIndex = i;
if(l maxIndex = l;
if(r maxIndex = r;
if(maxIndex != i)
{
swap(hn, i, maxIndex);
}

}

private static void swap(heapnd[] hn, int i, int maxIndex2) {
heapnd tmp = hn[i];
hn[i] = hn[maxIndex2];
hn[maxIndex2] = tmp;
}

class CustomException extends Exception{

private static final long serialVersionUID = 1L;
private String str;

public CustomException(String str)
{
this.str = str;
}

public String toString()
{
return str;
}
}

Reference:

http://www.geeksforgeeks.org/rearrange-a-string-so-that-all-same-characters-become-at-least-d-distance-away/

Given a string and a non-empty substring sub, Count sub in given string

Given a string and a non-empty substring sub, compute recursively the number of times that sub appears in the string, without the sub strings overlapping.

strCount("catcowcat", "cat") → 2
strCount("catcowcat", "cow") → 1
strCount("catcowcat", "dog") → 0




If i want to know that a substring exists in a given string or not, always try to use indexOf keyword rather than '==' operator. Because

String is immutable. i.e. Strings cannot be altered. When you alter a string (by adding to it for example), you are actually creating a new string object.




WorstCase:

static int strCount(String str, String sub) {

 int n = sub.length();
 int len = str.length();

 if(len < n) return 0;

 String tmp = str.substring(0,n);

 if(tmp.contains(sub))   // never use this in string (tmp == sub)
 {
 return strCount(str.substring(n, len), sub)+1;
  }
 else {
       return strCount(str.substring(1,len), sub);
 }

}


Better solution:

Use of  'indexOf ' string inbuild method:

static int strCount(String str, String sub)
{                                                
  return strCountUtil(str,sub,sub.length());
}


private static int strCountUtil(String str, String sub, int n)
{
int len = str.length();
if(len < n) return 0;
int index = str.indexOf(sub);
if(index >= 0)
{
return 1 + strCountUtil(str.substring(index+n), sub, n);
}

return 0;
}



private static int

"catdogccatca"
          |
 dogccatca
         |
     ca

An in-place algorithm for String Transformation

http://www.geeksforgeeks.org/an-in-place-algorithm-for-string-transformation/



static String stringTransformation(String str)
{
int n = str.length();
if(n == 0 || n == 1 || n == 2) return str;
char a[] = str.toCharArray();
int i,front = 2, rear, j;
for(i = 1; i < n && front {

rear = i;
j = front;
char tmp = a[j];
while (rear {
a[j] = a[j-1];
j--;
}
a[rear] = tmp;
front = front+2;
}

return new String(a);
}


Exercise: 
Given string in the form “abcdefg1234567″, convert it to “a1b2c3d4e5f6g7″ in-place and in O(n) time complexity.

Longest Palindromic Substring

http://www.geeksforgeeks.org/longest-palindromic-substring-set-2/



static String longestSubStr(String str)
{
int n = str.length();
if(n == 0 || n == 1)
{
return str;
}
int i , j = 0, k = 1, max = 0, start = 0, end = 0;

for (i = 1; i < n; i++)
{

k = i;
j = i-1;
while(k= 0 && str.charAt(j) == str.charAt(k))
{

j--; k++;

}
j = j+1;
k = k-1;
if((k-j) > max )
{
start = j;
end = k;
max = (k-j);
}
k = i+1;
j = i-1;
while (k=0 && str.charAt(j) == str.charAt(k))
{
j--; k++;
}

j = j+1;
k = k-1;
if((k-j) > max )
{
start = j;
end = k;
max = (k-j);
}

}

System.out.println("max length: "+ (max+1));
return str.substring(start, end+1);

}

Given a sequence of words, print all anagrams together

http://www.geeksforgeeks.org/given-a-sequence-of-words-print-all-anagrams-together-set-2/

Remove “b” and “ac” from a given string

string/http://www.geeksforgeeks.org/remove-a-and-bc-from-a-given-string/

First-non-repeating-character in string

http://www.geeksforgeeks.org/given-a-string-find-its-first-non-repeating-character/


static char firstNonRepeatedChar(String str)
{
int n = str.length();
if(n == 0) return '#';
if(n == 1) return str.charAt(0);

int hashArr[] = new int[266];
char charArr[] = new char[266];

for(int i = 0 ;  i < 266; i++)
{
hashArr[i] = 0;
}

for(int i = 0; i <  n; i++)
{
if(hashArr[str.charAt(i)]==0) charArr[i] = str.charAt(i);
hashArr[str.charAt(i)]++;
}

for(int i = 0; i < 266; i++)
{
if(hashArr[charArr[i]] == 1)
{
return charArr[i];
}
}

return '#';
}