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 '#';
}