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/