# Strings

```// Efficient : Time Complexity : O(n), Space Complexity : Θ(1)

static boolean isPalindrome(String str)
{

// Pointers pointing to the beginning
// and the end of the string
int begin = 0, end = str.length() - 1;

// While there are characters to compare
while (begin < end) {

// If there is a mismatch
if (str.charAt(begin) != str.charAt(end))
return false;

// Increment first pointer and
// decrement the other
begin++;
end--;
}

// Given string is a palindrome
return true;
}

// Naive : Time Complexity : Θ(n), Space Complexity : Θ(n)

static boolean isPalindrome(String str)
{
StringBuilder rev = new StringBuilder(str);
rev.reverse();  // StringBuilder is mutable & has a function called reverse

return str.equals(rev.toString());
}```
```// Iterative Solution : Time Complexity : O(n+m), Space Complexity : Θ(1)

static boolean isSubSeq(String s1, String s2, int n, int m){
int j = 0;
for(int i = 0; i < n && j < m; i++){
if(s1.charAt(i) == s2.charAt(j))
j++;
}

return j == m;
}

// Recursive Solution : Time Complexity : O(n+m), Space Complexity : Θ(n+m)

static boolean isSubSeq(String s1, String s2, int n, int m){
if( m == 0 )
return true;

if( n == 0 )
return false;

if ( s1.charAt(n-1) == s2.charAt(m-1) )
return isSubSeq(s1, s2, n-1, m-1);

else
return isSubSeq(s1, s2, n-1, m);
}```
```// Efficient : Time Complexity : O(n)

import java.util.*;
import java.io.*;

class GFG {

static final int CHAR=256;

static boolean areAnagram(String s1, String s2)
{
if (s1.length() != s2.length())
return false;

int[] count=new int[CHAR];
for(int i=0;i<s1.length();i++){
count[s1.charAt(i)]++;
count[s2.charAt(i)]--;
}

for(int i=0;i<CHAR;i++){
if(count[i]!=0)return false;
}
return true;
}

public static void main(String args[])
{
String str1 = "abaac";
String str2 = "aacba";
if (areAnagram(str1, str2))
System.out.println("The two strings are" + " anagram of each other");
else
System.out.println("The two strings are not" + " anagram of each other");
}
}

// Naive : Time Complexity : Θ(nlogn)

static boolean areAnagram(String s1, String s2)
{

if (s1.length() != s2.length())
return false;

char a1[]=s1.toCharArray();
Arrays.sort(a1);
s1=new String(a1);
char a2[]=s2.toCharArray();
Arrays.sort(a2);
s2=new String(a2);

return s1.equals(s2);
} ```
```// Efficient Approach-2 : Time & Space similar to previous method

static final int CHAR=256;
static int leftMost(String str)
{
boolean[] visited=new boolean[CHAR];
int res=-1;
for(int i=str.length()-1;i>=0;i--){
if(visited[str.charAt(i)])
res=i;
else
visited[str.charAt(i)]=true;
}

return res;
}

// One Traversal
// Efficient Approach-1 : Time Complexity : O(n + CHAR), Auxiliary Space : O(CHAR)

static final int CHAR=256;
static int leftMost(String str)
{
int[] fIndex=new int[CHAR];
Arrays.fill(fIndex,-1);
int res=Integer.MAX_VALUE;
for(int i=0;i<str.length();i++){
int fi=fIndex[str.charAt(i)];
if(fi==-1)
fIndex[str.charAt(i)]=i;
else
res=Math.min(res,fi);
}

return (res==Integer.MAX_VALUE)?-1:res;
}

// Better Approach : Time Complexity : O(n) but requires two loops for input string

static final int CHAR=256;
static int leftMost(String str)
{
int[] count=new int[CHAR];
for(int i=0;i<str.length();i++){
count[str.charAt(i)]++;
}
for(int i=0;i<str.length();i++){
if(count[str.charAt(i)]>1)return i;
}
return -1;
}

// Naive Code : Time Complexity : O(n^2)

static int leftMost(String str)
{
for(int i=0;i<str.length();i++){
for(int j=i+1;j<str.length();j++){
if(str.charAt(i)==str.charAt(j))return i;
}
}
return -1;
}```
```// One Traversal
// Efficient Approach-1 : Time Complexity : O(n)

static final int CHAR=256;
static int nonRep(String str)
{
int[] fI=new int[CHAR];
Arrays.fill(fI,-1);

for(int i=0;i<str.length();i++){
if(fI[str.charAt(i)]==-1)
fI[str.charAt(i)]=i;
else
fI[str.charAt(i)]=-2;
}
int res=Integer.MAX_VALUE;
for(int i=0;i<CHAR;i++){
if(fI[i]>=0)res=Math.min(res,fI[i]);
}
return (res==Integer.MAX_VALUE)?-1:res;
}

// Two Traversal
// Better Approach : Time Complexity : O(n)

static final int CHAR=256;
static int nonRep(String str)
{
int[] count=new int[CHAR];
for(int i=0;i<str.length();i++){
count[str.charAt(i)]++;
}
for(int i=0;i<str.length();i++){
if(count[str.charAt(i)]==1)return i;
}
return -1;
}

// Naive Code : Time Complexity : O(n^2)

static int nonRep(String str)
{
for(int i=0;i<str.length();i++){
boolean flag=false;
for(int j=0;j<str.length();j++){
if(i!=j&&str.charAt(i)==str.charAt(j)){
flag=true;
break;
}
}
if(flag==false)return i;
}
return -1;
}```
```// Efficient Approach :
// NOTE : The code doesn’t handle the cases when the string starts with space.

import java.util.*;
import java.io.*;

class GFG {

static void reverse(char str[],int low, int high)
{
while(low<=high)
{
//swap
char temp=str[low];
str[low]=str[high];
str[high]=temp;

low++;
high--;
}
}

static void reverseWords(char str[],int n){
int start=0;
for(int end=0;end<n;end++){
if(str[end]==' '){
reverse(str,start,end-1);
start=end+1;
}
}
reverse(str,start,n-1);
reverse(str,0,n-1);
}

public static void main(String args[])
{   String s = "Welcome to Gfg";int n=s.length();
char[] str = s.toCharArray();
System.out.println("After reversing words in the string:");
reverseWords(str,n);
System.out.println(str);
}
} ```
```m -> Pattern length
n -> Text length
1 <= m <=n
---------------------------------------------------------------------------------------------------

// NO PREPROCESSING

Naive : O((n-m+1)*m)

Naive (When all characters of Pattern are distinct) : O(n)
---------------------------------------------------------------------------------------------------

// PREPROCESS PATTERN

Rabin Karp : O((n-m+1)*m)  // But, better then naive on average

KMP Algorithm : O(n)
---------------------------------------------------------------------------------------------------

// PREPROCESS TEXT

Suffix Tree : O(m)```
```import java.util.*;
import java.io.*;

class GFG {

static void patSearchinng(String txt,String pat)
{
int m=pat.length();
int n=txt.length();
for(int i=0;i<=(n-m);i++){
int j;
for(j=0;j<m;j++)
if(pat.charAt(j)!=txt.charAt(i+j))
break;

if(j==m)
System.out.print(i+" ");
}
}

public static void main(String args[])
{   String txt = "ABCABCD";String pat="ABCD";
System.out.print("All index numbers where pattern found: ");
patSearchinng(txt,pat);
}
} ```
```import java.util.*;
import java.io.*;

class GFG {

static void patSearchinng(String txt,String pat)
{
int m=pat.length();
int n=txt.length();
for(int i=0;i<=(n-m); )
{
int j;
for(j=0;j<m;j++)
if(pat.charAt(j)!=txt.charAt(i+j))
break;

if(j==m)
System.out.print(i+" ");
if(j==0)
i++;
else
i=(i+j);
}
}

public static void main(String args[])
{   String txt = "ABCABCD";String pat="ABCD";
System.out.print("All index numbers where pattern found: ");
patSearchinng(txt,pat);
}
} ```
```import java.util.*;
import java.io.*;

class GFG {
static final int d=256;
static final int q=101;
static void RBSearch(String pat,String txt,int M, int N)
{
//Compute (d^(M-1))%q
int h=1;
for(int i=1;i<=M-1;i++)
h=(h*d)%q;

//Compute p and to
int p=0,t=0;
for(int i=0;i<M;i++){
p=(p*d+pat.charAt(i))%q;
t=(t*d+txt.charAt(i))%q;
}

for(int i=0;i<=(N-M);i++){
//Check for hit
if(p==t){
boolean flag=true;
for(int j=0;j<M;j++)
if(txt.charAt(i+j)!=pat.charAt(j)){flag=false;break;}
if(flag==true)System.out.print(i+" ");
}
//Compute ti+1 using ti
if(i<N-M){
t=((d*(t-txt.charAt(i)*h))+txt.charAt(i+M))%q;
if(t<0)t=t+q;
}
}

}

public static void main(String args[])
{   String txt = "GEEKS FOR GEEKS";String pat="GEEK";
System.out.print("All index numbers where pattern found: ");
RBSearch(pat,txt,4,15);
}
} ```
```// Efficient Code O(n)

import java.util.*;
import java.io.*;

class GFG {

static void fillLPS(String str, int lps[])
{
int n=str.length(),len=0;
lps[0]=0;
int i=1;
while(i<n){
if(str.charAt(i)==str.charAt(len))
{len++;lps[i]=len;i++;}
else
{if(len==0){lps[i]=0;i++;}
else{len=lps[len-1];}
}
}
}

public static void main(String args[])
{   String txt = "abacabad";int[] lps=new int[txt.length()];
fillLPS(txt,lps);
for(int i=0;i<txt.length();i++){
System.out.print(lps[i]+" ");
}
}
}

// Naive Code O(n^3)

import java.util.*;
import java.io.*;

class GFG {

static int longPropPreSuff(String str, int n)
{
for(int len=n-1;len>0;len--){
boolean flag=true;
for(int i=0;i<len;i++)
if(str.charAt(i)!=str.charAt(n-len+i))
flag=false;

if(flag==true)
return len;
}
return 0;
}

static void fillLPS(String str, int lps[]){
for(int i=0;i<str.length();i++){
lps[i]=longPropPreSuff(str,i+1);
}
}

public static void main(String args[])
{   String txt = "abacabad";int[] lps=new int[txt.length()];
fillLPS(txt,lps);
for(int i=0;i<txt.length();i++){
System.out.print(lps[i]+" ");
}
}
} ```
```import java.util.*;
import java.io.*;

class GFG {

static void fillLPS(String str, int lps[])
{
int n=str.length(),len=0;
lps[0]=0;
int i=1;
while(i<n){
if(str.charAt(i)==str.charAt(len))
{len++;lps[i]=len;i++;}
else
{if(len==0){lps[i]=0;i++;}
else{len=lps[len-1];}
}
}
}

static void KMP(String pat,String txt)
{
int N=txt.length();
int M=pat.length();
int[] lps=new int[M];
fillLPS(pat,lps);
int i=0,j=0;
while(i<N){
if(pat.charAt(j)==txt.charAt(i)){i++;j++;}

if (j == M) {
System.out.println("Found pattern at index " + (i - j));
j = lps[j - 1];
}
else if (i < N && pat.charAt(j) != txt.charAt(i)) {
if (j == 0)
i++;
else
j = lps[j - 1];
}
}
}

public static void main(String args[])
KMP(pat,txt);
}

} ```
```import java.util.*;
import java.io.*;

class GFG {

static boolean areRotations(String s1,String s2)
{
if(s1.length()!=s2.length())
return false;

return ((s1+s1).indexOf(s2)>=0);
}

public static void main(String args[])
{
String s1 = "ABCD";String s2="CDAB";

if(areRotations(s1,s2)){
System.out.println("Strings are rotations of each other");
}
else{
System.out.println("Strings are not rotations of each other");
}
}
} ```
```// Efficient Code : O(m+(n-m) * CHAR)  or  since m<n so,
// Time : O(n * CHAR),  Aux. Space : Θ(CHAR)

import java.util.*;
import java.io.*;

class GFG {

static final int CHAR=256;
static boolean areSame(int CT[],int CP[])
{
for(int i=0;i<CHAR;i++){
if(CT[i]!=CP[i])return false;
}
return true;
}

static boolean isPresent(String txt,String pat)
{
int[] CT=new int[CHAR];
int[] CP=new int[CHAR];
for(int i=0;i<pat.length();i++) {
CT[txt.charAt(i)]++;
CP[pat.charAt(i)]++;
}
for(int i=pat.length();i<txt.length();i++) {
if(areSame(CT,CP))return true;
CT[txt.charAt(i)]++;
CT[txt.charAt(i-pat.length())]--;
}
return false;
}

public static void main(String args[])
{
String txt = "geeksforgeeks";
String pat = "frog";
if (isPresent(txt, pat))
System.out.println("Anagram search found");
else
}
}

// Naive Code : O((n-m+1)*m)

import java.util.*;
import java.io.*;

class GFG {

static final int CHAR=256;
static boolean areAnagram(String pat, String txt,int i)
{
int[] count=new int[CHAR];
for(int j=0; j<pat.length(); j++)
{
count[pat.charAt(j)]++;
count[txt.charAt(i+j)]--;
}
for(int j=0; j<CHAR; j++)
{
if(count[j]!=0)
return false;
}
return true;
}

static boolean isPresent(String txt,String pat)
{
int n=txt.length();
int m=pat.length();
for(int i=0;i<=n-m;i++)
{
if(areAnagram(pat,txt,i))
return true;
}
return false;
}

public static void main(String args[])
{
String txt = "geeksforgeeks";
String pat = "frog";
if (isPresent(txt, pat))
System.out.println("Anagram search found");
else
}
} ```
```import java.util.*;
import java.io.*;

class GFG {

static final int CHAR=256;
static int fact(int n)
{
return (n <= 1) ? 1 : n * fact(n - 1);
}

static int lexRank(String str)
{
int res = 1;
int n=str.length();
int mul= fact(n);
int[] count=new int[CHAR];
for(int i=0;i<n;i++)
count[str.charAt(i)]++;
for(int i=1;i<CHAR;i++)
count[i]+=count[i-1];
for(int i=0;i<n-1;i++){
mul=mul/(n-i);
res=res+count[str.charAt(i)-1]*mul;
for(int j=str.charAt(i);j<CHAR;j++)
count[j]--;
}
return res;
}

public static void main(String args[])
{
String str = "STRING";
System.out.print(lexRank(str)); // OUTPUT : 598
}
} ```
```// Efficient Code O(n) :

import java.util.*;
import java.io.*;

class GFG {

static int longestDistinct(String str)
{
int n = str.length();
int res = 0;
int prev[]=new int[256];
Arrays.fill(prev,-1);
int i=0;
for (int j = 0; j < n; j++)
{
i=Math.max(i,prev[str.charAt(j)]+1);
int maxEnd=j-i+1;
res=Math.max(res,maxEnd);
prev[str.charAt(j)]=j;
}
return res;
}

public static void main(String args[])
{
String str = "geeksforgeeks";
int len = longestDistinct(str);  // OUTPUT : 7
System.out.print("The length of longest distinct characters substring is "+ len);
}
}

// Better Approach O(n2) :

import java.util.*;
import java.io.*;

class GFG {

static int longestDistinct(String str)
{
int n = str.length();
int res = 0;
for (int i = 0; i < n; i++){
boolean visited[]=new boolean[256];
for(int j=i;j<n;j++){
if(visited[str.charAt(j)]==true){
break;
}
else{
res=Math.max(res,j-i+1);
visited[str.charAt(j)]=true;
}
}
}
return res;
}

public static void main(String args[])
{
String str = "geeksforgeeks";
int len = longestDistinct(str);  // OUTPUT : 7
System.out.print("The length of longest distinct characters substring is "+ len);
}
}

// Naive Code O(n3) :

import java.util.*;
import java.io.*;

class GFG {

static boolean areDistinct(String str, int i, int j)
{
boolean visited[]=new boolean[256];

for (int k = i; k <= j; k++) {
if (visited[str.charAt(k)] == true)
return false;
visited[str.charAt(k)] = true;
}
return true;
}

static int longestDistinct(String str)
{
int n = str.length();
int res = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
if (areDistinct(str, i, j))
res = Math.max(res, j - i + 1);
return res;
}

public static void main(String args[])
{
String str = "geeksforgeeks";
int len = longestDistinct(str);  // OUTPUT : 7
System.out.print("The length of longest distinct characters substring is "+ len);
}
} ```