Problem - Find maximal palindromic subsequence/substring of given string.

Following is one of the solution. But it is not efficient one.
It takes O(n²) for both time and space.

Write a program to print the following pattern :

1
3*2
4*5*6
10*9*8*7

______________________________________________________________

Question - Reverse an array in specified group size. e.g. Array - 1,2,3,4,5,6,7,8,9 and grpSize -3 then output 3,2,1,6,5,4,9,8,7

Question - Given Two strings, return true if they are one edit away from each other else return false. An edit is insert/replace/delete a character. Ex. {"abc","ab"}->true, {abc","adc"}->true, {"abc","cab"}->false

A number x supports a number (x+b) where b is the number of set bits in binary representation of x, like if x = 3 then x supports (3+2)=5 as 3 has 2 1’s in its binary representation. Now you are provided with an array of numbers you have to print the supported number corresponding to each of the given number.

Program to form a HashMap out of given String

For example:
Input : name=ashish&age=24&company=kyubatau&city=pune
output : a HashMap containing LHS values as Keys and RHS values as Values

//Program to form a HashMap out of given String 

//O(n)

//Program to form a HashMap out of given String 
//O(n)

import java.util.*;

public class StringMap{
static public void main(String args[]){
System.out.println(new StringMap().getStringMap("name=ashish&age=24&company=kyubatau&city=pune"));
}

public HashMap<String,String> getStringMap(String str){

String flag = "key";
String myKey = "", myVal = "";
HashMap<String,String> pairs = new HashMap<>();


for(int i=0 ;  i<str.length()  ;  i++)
{
String curr = String.valueOf(str.charAt(i));


if(curr.equals("=" ))
{
flag = "value";
continue;
}

if(curr.equals("&"))
{
pairs.put(myKey,myVal);
flag = "key";
myKey = "";
myVal = "";
continue;
}

if(flag.equals("key"))
myKey = myKey + str.charAt(i);
else
if(flag.equals("value"))
myVal = myVal + str.charAt(i);
}

pairs.put(myKey,myVal);

return pairs;
}
}


output:

{city=pune, name=ashish, company=kyubatau, age=24}

Finding sum of all digits present in a string

//Finding the sum of all digits present in a string 

public class DigitSum{
public static void main(String args[]){
String str = "asd9od1dfjhd7sdhdsf21df6"; //Sum is 26
int sum = 0;

for(int i=0 ; i<str.length() ; i++)
{
if(str.charAt(i)>=48 && str.charAt(i)<=57)
sum = sum + Integer.parseInt(String.valueOf(str.charAt(i)));
}

System.out.println(sum);
}
}



____________________________________________________________________________

Variant - 1 : Find Sum of all digits numbers present in a string and separated by space from other characters.
For e.g.
"1  Pappu is 16 years and read in 11 std. 2 of his friends are nuts.He has 8 siblings.He eats 89 pancakes everyday. 7 90"

Sum = 224

//Program to find sum of numbers present in a string and separated by space

public class DigitSum1{
public static void main(String args[]){

System.out.println(new DigitSum1().getSum("1 Ravi is 16 years and read in 11 std. 2 of his friends are nuts.He has 8 siblings.He eats 89 pancakes everyday. 7 90")); //224
}

public int getSum(String str){

String myNum="";
int sum = 0;
String prev = "nan";

//to read string character by character
for(int i=0 ; i<str.length() ; i++)
{

//if it is a digit, keep forming a number
if(str.charAt(i)>=48 && str.charAt(i)<=57)
{
myNum = myNum + String.valueOf(str.charAt(i));
prev = "number";
continue;
}

//if it is a space, add the number to variable sum
else
{
if(String.valueOf(str.charAt(i)).equals(" "))
{
try{
sum = sum + Integer.parseInt(myNum);
}
catch(NumberFormatException nfe){
myNum="0";
}
myNum="";
}
}

}

//Once execution come out of loop there may be a number left which wasn't added, so add it too
try{
sum = sum + Integer.parseInt(myNum);
}
catch(NumberFormatException nfe){
myNum="0";
}


return sum;
}
}

__________________________________________________________________________

Another way of implementing above

public class DigitSum2{
public static void main(String args[]){

System.out.println(new DigitSum2().getSum("1 Ravi is 16 years and read in 11 std. 2 of his friends are nuts.He has 8 siblings.He eats 89 pancakes everyday. 7 90"));
}

public int getSum(String str){

String myNum="";
int sum = 0;
String prev = "nan";


for(int i=0 ; i<str.length() ; i++)
{

if(str.charAt(i)>=48 && str.charAt(i)<=57)
{
myNum = myNum + String.valueOf(str.charAt(i));
prev = "number";
continue;
}

else
{
if(String.valueOf(str.charAt(i)).equals(" ") && prev.equals("number"))
{
sum = sum + Integer.parseInt(myNum);
prev = "nan";
myNum="";
}
}

}

if(prev.equals("number")) sum = sum + Integer.parseInt(myNum);
return sum;
}
}

Finding Second Highest Number in an Integer array

//Program to find Second highest number in an array - O(n^2)

public class SecHigh{
public static void main(String args[]){

int arr[] = {9,13,43,99,0,19,100,78,63,55}; //99 is second highest
int secHi = 0, counter = 0;

for(int i=0 ; i<arr.length ; i++)
{
counter = 0;
for(int j=0 ; j<arr.length ; j++)
{
if(arr[i]<arr[j])
counter++;
}

if(counter == 1)
System.out.println(arr[i]);

}
}
}


________________________________________________________________________________

BETTER SOLUTION

//Program to find second highest number in an array - O(n)

public class SecHigh1{
public static void main(String args[]){
int arr[] = {12,100,1,78,65,39,79,99,81,91};

int highest = Integer.MIN_VALUE;
int secHi = Integer.MIN_VALUE;

for(int i=0 ; i<arr.length ; i++)
{
if(highest<arr[i])
{
secHi = highest;
highest = arr[i];
}
else
{
if(secHi<arr[i])
secHi = arr[i];
}
}

System.out.println(secHi);

}
}

Java access specifiers and access modifiers

Acording to java language specification, Java have following access modifiers :
1. Public
2. Protected
3. Default
4. Private

Reference : https://docs.oracle.com/javase/tutorial/java/javaOO/accesscontrol.html

And, Java 'access specifier' term is used synonymously with 'access modifier'.

But for the sake of understanding let's categorized as follows :

1. Java access modifiers :
    (a). Public
    (b). Protected
    (c). Default
    (d). Private

You can find the description of above specifiers at many places.

2. Other keywords that affects visibilty/access usually called non access modifiers :

[i]. For variables:
    (a). static
    (b). final
    (c). native
    (d). volatile
    (e). abstract
    (f). transient

[ii]. For methods:
    (a). abstract
    (b). final
    (c). synchronized
    (d). static

[iii[. For classes:
   (a). abstract
   (b). strictfp
   (c). final
  

Q.9 - Write a program to demonstrate the addition of two strings digitwise.

public class StringAdd{
 public static void main(String args[]){
  String a = "9999999999999999999";
  String b = "2222222222222222222";
  int c1[] = new int[b.length()];
  try
  {
   for(int i=0;i<a.length() && i<b.length();i++)
    c1[i] = Integer.parseInt(String.valueOf(a.charAt(i))) + Integer.parseInt(String.valueOf(b.charAt(i)));
  }

  catch(NumberFormatException e)
  {
   System.out.println("Please give strings containing numeric characters only");
   return;
  }
  System.out.println(new StringAdd().toString(c1));
 }

 //Override toString() method to convert int array to string
 public String toString(int arr[]){
  String str="";
  for(int k:arr)
   str = str + Integer.toString(k);
  return str;
 }
}

Q.8 - Write a program to determine whether a string is cyclic shift (rotation) of other.

public class Rotation{
public static void main(String args[]){

System.out.println(Rotation.isRotation("ashish","hishas"));
}

static boolean isRotation(String actual, String checkString){

if(actual.length() != checkString.length())
return false;

if((checkString+checkString).indexOf(actual)!=-1)
return true;
else
return false;
}
}

Q.7 - Program to find out first non repeating character in a string.

public class FirstUnique{
public static void main(String args[]){
new FirstUnique().getUnique("stroirotatous");
}

public void getUnique(String str){
int arr[]  = new int[255];

for(int i = 0 ; i<str.length() ; i++)
{
arr[str.charAt(i)]++;
}

for(int j = 0; j<str.length(); j++)
{
if(arr[str.charAt(j)] == 1)
{
System.out.println((char)j);
return;
}
}

}
}

Q.6 - Determine whether a given string is palindrome or not

public class Palindrome{
public static void main(String args[]){
char str[] = args[0].toCharArray();
int strLength = str.length-1;

for(int i=0, j=strLength;i<=strLength/2;i++,j--)
{
if(str[i] != str[j])
{
System.out.println("No");
return;
}
else
continue;
}

System.out.println("Palindrome");

}
}

Q.5 - 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.

public class StringCompression{
   public static void main(String args[]){
      System.out.println(new StringCompression().compressString("cccconnttttttiiiinnnummmmmmmmmmm")); //c4o1n2t6i4n3m11
      System.out.println(new StringCompression().compressString("Ashish")); //Ashish
}

  public String compressString(String str){
      String newString = "";
      char curr = ' ',prev = ' ';
      int count = 0;

      curr = str.charAt(0);
   
      for(int i=0 ; i<str.length() ; i++)
      {
         prev = curr;
         curr = str.charAt(i);
         if(prev == curr)
           count++;
 else
 {
    newString = newString + prev + String.valueOf(count);
    count = 1;
 }
      }

newString = newString + prev + String.valueOf(count);

if(!(newString.length() < str.length()))
   return str;
return newString;
   }
}

_______________________________________________________________________

Output:
c4o1n2t6i4n3u1m11
Ashish

Q.4 - Program to implement string reversal in java recursively

//Program to implement string reversal in java recursively

public class ReverseString{
   public static int i = 0;
   public static void main(String args[]){
      System.out.println(ReverseString.revStr("repeed gniggid tuo ti deelB"));
   }

   public static String revStr(String str){
      char curr = ' ';
      String revStr = "";
      if(str.length() == 1)
                    return str;
              curr = str.charAt(0);
      revStr = revStr(str.substring(1,str.length()));
      revStr += curr;

      return revStr;
   }
}

Q.3 - Implement an algorithm to determine if a string has all unique characters.

//Implement an algorithm to determine if a string has all unique characters.  
// This code has O(n^2) time complexity. [We can find a better solution]

public class UniqueChar{
public static void main(String args[])
{
UniqueChar uc = new UniqueChar();

System.out.println("Ashish : " + uc.detUnique("Ashish"));
System.out.println("Vishal : " + uc.detUnique("Vishal"));
System.out.println("Vinod : " + uc.detUnique("Vinod"));
System.out.println("Priyanka : " + uc.detUnique("Priyanka"));

}

public boolean detUnique(String string)
{
char charArray[]= string.toCharArray();
int count = 0;

for(char c : charArray)
{
count = 0;
for(char d : charArray)
if(d==c)
count++;

if(count>1)
return false;
}

return true;
}
}

____________________________________________________________

THE BETTER SOLUTION

//Implement an algorithm to determine if a string has all unique characters.
//The time complexity of this code is O(n), where n is the length of the string.
//The space complexity is O(1)

public class UniqueChar2
{
   public static void main(String args[])
   {
      UniqueChar2 obj = new UniqueChar2();
      System.out.println(obj.isUniqueChar("@n@rchy"));
   }

   public boolean isUniqueChar(String str)
   {
      if(str.length()>256) return false;

       boolean char_set[] = new boolean[256];
       for(int i=0;i<str.length();i++)
       {
          int val = str.charAt(i);
         if(char_set[val]) //Already found this char in string
            return false;

         char_set[val] = true;
       }

return true;
   }
}

Question - 2 : Given two strings, write a method to decide if one is a permutation of the other.

//To check whether a given string is permutation of other string
public class Permutation{
public static void main(String args[]){
if(new Permutation().isPermutation("tiger","igert"))
System.out.println("Yes,strings are permutation of each other.");
else
System.out.println("No,strings aren't permutation of each other.");
}

  public boolean isPermutation(String str1,String str2){
char arr[] = new char[255];
char brr[] = new char[255];
int j = 0;
if(str1.length() != str2.length())
return false;
for(int i=0 ; i<str1.length() ; i++)
{
arr[str1.charAt(i)]++;
brr[str2.charAt(i)]++;
}
                
//To check whether frequency of each character is same for both strings
for(j=0 ; j<arr.length && arr[j] == brr[j]; j++);

if(j!=255)
return false;
else
return true;
}
}


______________________________________________________________

Now implement the above with following constraint:

Do not use any additional data structure like array.

//To check whether a given string is permutation of other string
public class Permutation1{
   public static void main(String args[]){
if(new Permutation1().isPermut("ashish","shshii"))
        System.out.println("These two are permutation of each other");
else
        System.out.println("These aren't permutation of each other");
}

public boolean isPermut(String str1, String str2){
if(str1.length()!=str2.length())
return false;

for(int i=0 ; i<str1.length() ; i++)
{
if(str1.indexOf(str2.charAt(i)) == -1)
return false;

if(str2.indexOf(str1.charAt(i)) == -1)
return false;
}

return true;
}

Question - 1 : Write a java program to find a particular string in another string and replace all occurrences of it with another string.

Constraints :
(a) Time complexity should be O(n)
(b) Should not use replace() or any other such function which directly solve the problem.

public class FindRep {
 public static void main(String[] args) {
  new FindRep().findRepStr("We go in a field, but we don't go deep in it and wish to go in another field", "in", "out");
  new FindRep().findRepStr("A quick over brown fox over jumped over the over lazy dog over over over", "over", "z");
 }

 public void findRepStr(String str, String findStr, String repStr) {
  String s1 = "", s2 = "", s3 = "";
  int index = 0;

  while (index != -1) {
   if ((index = str.indexOf(findStr)) != -1) {
    s1 = str.substring(0, index); //Substring before of findString
    s2 = str.substring(index, str.length()).substring(findStr.length(), str.length() - s1.length()); //Substring after of findString
    str = s1 + repStr + s2;
   }
  }
  System.out.println(str);
 }
}