✦ DSA CHEAT SHEET (JAVA) – ARRAYS (Part 1) ✦

Page 1

1 FIND SMALLEST IN ARRAY 2 FIND LARGEST IN ARRAY 3 2ND SMALLEST & 2ND LARGEST
Logic : Track min while iterating Logic : Track max while iterating Logic : Two-pass or single-pass tracking

int min = arr[0]; int max = arr[0]; int s1=INF, s2=INF; // smallest
for(int i=1; i<n; i++) for(int i=1; i<n; i++) int l1=-INF, l2=-INF; // largest
if(arr[i] < min) if(arr[i] > max) for(int x : arr) {
min = arr[i]; max = arr[i]; if(x<s1){s2=s1;s1=x;}
• Init min = arr[0], loop from index 1 • Init max = arr[0], loop from index 1 else if(x<s2) s2=x;
• Time: O(n) Space: O(1) • Time: O(n) Space: O(1) if(x>l1){l2=l1;l1=x;}
else if(x>l2) l2=x; }
• s2 = 2nd smallest, l2 = 2nd largest
4 REVERSE A GIVEN ARRAY 5 COUNT FREQUENCY OF ELEMENTS • Time: O(n) Space: O(1)
Logic : Two-pointer swap from both ends Logic : Use HashMap for O(n) counting

int l=0, r=n-1; Map<Integer,Integer> map 6 REARRANGE INC-DEC ORDER

while(l < r) { = new HashMap<>(); Logic : Sort, then place alternately
int tmp=arr[l]; for(int x : arr)
arr[l++]=arr[r]; [Link](x, [Link](arr);
arr[r--]=tmp; } [Link](x,0)+1); // First half ascending,
• Swap arr[l] & arr[r], move inward • [Link](key) → frequency of key // second half descending
• Time: O(n) Space: O(1) • Time: O(n) Space: O(n) int[] res = new int[n];
int l=0,r=n-1,i=0;
while(l<=r){
7 CALCULATE SUM OF ARRAY 8 ROTATE ARRAY BY K (REVERSAL) res[i++]=arr[l++];
Logic : Accumulate sum in single pass Logic : Reverse subarrays then whole array if(l<=r) res[i++]=arr[r--];}
• Time: O(n log n) Space: O(n)
long sum = 0; k = k % n;
for(int x : arr) reverse(arr,0,n-1);
sum += x; reverse(arr,0,k-1); 9 AVERAGE OF ARRAY ELEMENTS
• Use long to avoid int overflow reverse(arr,k,n-1); Logic : sum / n
• Time: O(n) Space: O(1) // void reverse(int[]a,int l,int r)
// { while(l<r) swap(a,l++,r--); } double sum = 0;
• Right rotate: reverse all → split & for(int x : arr) sum += x;
reverse double avg = sum / n;
• Time: O(n) Space: O(1) • Cast to double before dividing
• Time: O(n) Space: O(1)

DSA Java Cheat Sheet | Page 1 of 11

✦ DSA CHEAT SHEET (JAVA) – ARRAYS (Part 2) ✦
Page 2

10 FIND MEDIAN OF ARRAY 11 REMOVE DUPLICATES (SORTED) 12 REMOVE DUPLICATES (UNSORTED)

Logic : Sort, pick middle element(s) Logic : Two-pointer in-place technique Logic : Use LinkedHashSet to preserve order

[Link](arr); int j = 0; Set<Integer> seen

if(n%2==1) for(int i=1; i<n; i++) = new LinkedHashSet<>();
median = arr[n/2]; if(arr[i] != arr[j]) for(int x : arr) [Link](x);
else arr[++j] = arr[i]; // seen contains unique elements
median=(arr[n/2-1]+arr[n/2])/2.0; // new length = j+1 // in insertion order
• Odd n → middle; Even n → avg of two mid • j tracks last unique index • LinkedHashSet: unique + ordered
• Time: O(n log n) Space: O(1) • Time: O(n) Space: O(1) • Time: O(n) Space: O(n)

13 ADDING ELEMENT IN ARRAY 14 FIND ALL REPEATING ELEMENTS 15 FIND NON-REPEATING ELEMENTS
Logic : Use ArrayList for dynamic insertion Logic : HashMap: find elements with freq > 1 Logic : HashMap: find elements with freq == 1

List<Integer> list Map<Integer,Integer> freq // Build frequency map (same as above)

= new ArrayList<>([Link](arr)); = new HashMap<>(); for(var e : [Link]())
[Link](pos, element); // at index for(int x:arr) if([Link]() == 1)
[Link](element); // at end [Link](x,1,Integer::sum); [Link]([Link]());
• Fixed array: shift elements right first for(var e:[Link]()) • Time: O(n) Space: O(n)
• Time: O(n) shift Space: O(1) if([Link]()>1)
print([Link]());
• Time: O(n) Space: O(n) 16 FIND ALL SYMMETRIC PAIRS
17 MAXIMUM PRODUCT SUBARRAY Logic : HashMap: store first → check reverse
Logic : Track max & min (negatives flip sign)
18 REPLACE ELEMENTS BY RANK Map<Integer,Integer> map=new HashMap<>();
int maxP=arr[0],minP=arr[0],res=arr[0]; Logic : Sort copy → map value to rank for(int[]p : pairs) {
for(int i=1;i<n;i++){ if([Link](p[1])
int tmp=maxP; int[] sorted = [Link](); && [Link](p[1])==p[0])
maxP=[Link](arr[i], [Link](sorted); print(p[1]+","+p[0]);
[Link](maxP*arr[i],minP*arr[i])); Map<Integer,Integer> rank=new HashMap<>(); else [Link](p[0],p[1]); }
minP=[Link](arr[i], int r=1; • (a,b) and (b,a) are symmetric pairs
[Link](tmp*arr[i],minP*arr[i])); for(int x:sorted) • Time: O(n) Space: O(n)
res=[Link](res,maxP); } if()

• Keep both max & min (negative * negative [Link](x,r++);

= +ve) for(int i=0;i<n;i++) arr[i]=[Link](arr[i]);
• Time: O(n) Space: O(1) • Time: O(n log n) Space: O(n)

DSA Java Cheat Sheet | Page 2 of 11

✦ DSA CHEAT SHEET (JAVA) – ARRAYS (Part 3) ✦
Page 3

19 SORT ELEMENTS BY FREQUENCY 20 LEFT & RIGHT ROTATION BY K 21 EQUILIBRIUM INDEX OF ARRAY
Logic : Freq map → sort by freq desc Logic : Use modulo to handle k > n Logic : leftSum == rightSum at index i

Map<Integer,Integer> freq=new HashMap<>(); k = k % n; long total = sum of arr;

for(int x:arr) [Link](x,1,Integer::sum); // Left rotate by k: long leftSum = 0;
Integer[] box = ...; // arr as Integer[] int[] left = [Link]( for(int i=0;i<n;i++){
[Link](box,(a,b)-> [Link](arr,k,n), total -= arr[i];
[Link](b)-[Link](a)); [Link](arr,0,k)).toArray(); if(leftSum == total) return i;
• Tie-break: sort by value if freq equal // Right rotate by k: leftSum += arr[i]; }
• Time: O(n log n) Space: O(n) // treat as left rotate by (n-k) • Exclude arr[i] from both sides
• Time: O(n) Space: O(n) [with new array] • Time: O(n) Space: O(1)

22 CIRCULAR ROTATION BY K
Logic : Same as right rotation (mod n) 23 SORT ARRAY BY ANOTHER ARRAY 24 SEARCH ELEMENT IN ARRAY
Logic : Use order array index as sort key Logic : Linear search O(n) or Binary search O(log n)
k = k % n;
int[] res = new int[n]; Map<Integer,Integer> pos=new HashMap<>(); // Linear Search:
for(int i=0;i<n;i++) for(int i=0;i<[Link];i++) for(int i=0;i<n;i++)
res[(i+k)%n] = arr[i]; [Link](order[i],i); if(arr[i]==target) return i;

• Element at i → moves to (i+k)%n // Sort arr using comparator: // Binary Search (sorted array):

• Time: O(n) Space: O(n) [Link](arr,(a,b)-> int l=0,r=n-1;

[Link](a,MAX) while(l<=r){
-[Link](b,MAX)); int m=(l+r)/2;
25 CHECK IF ARRAY IS SUBSET • Elements not in order go to end if(arr[m]==t) return m;
Logic : Add A to HashSet; check all of B • Time: O(n log n) Space: O(n) else if(arr[m]<t) l=m+1;
else r=m-1; }
Set<Integer> setA = new HashSet<>();
• Use Binary Search only on sorted arrays
for(int x : A) [Link](x); 1 BUBBLE SORT ALGORITHM
for(int x : B) Logic : Repeatedly swap adjacent out-of-order elements
if() 2 SELECTION SORT ALGORITHM
return false; // B not subset of A for(int i=0;i<n-1;i++){ Logic : Find min in unsorted, place at front
return true; boolean swapped=false;
• B is subset of A if every element of B is for(int j=0;j<n-i-1;j++) for(int i=0;i<n-1;i++){
in A if(arr[j]>arr[j+1]){ int minIdx=i;
• Time: O(n+m) Space: O(n) swap(arr,j,j+1); for(int j=i+1;j<n;j++)
swapped=true; } if(arr[j]<arr[minIdx])
if(!swapped) break; // optimized minIdx=j;
} swap(arr,i,minIdx); }
• Best: O(n) | Avg/Worst: O(n^2) | Stable ✓ • Always O(n^2) | Not stable | Min swaps

DSA Java Cheat Sheet | Page 3 of 11

✦ DSA CHEAT SHEET (JAVA) – NUMBERS (Part 1) ✦
Page 4

1 CHECK PALINDROME NUMBER 2 PALINDROMES IN GIVEN RANGE 3 CHECK IF NUMBER IS PRIME

Logic : Reverse digits, compare with original Logic : Check each number in [l, r] Logic : Check divisors from 2 to √n

int orig = n, rev = 0; for(int i=l; i<=r; i++) if(n < 2) return false;
while(n > 0) { if(isPalindrome(i)) for(int i=2; i*i<=n; i++)
rev = rev*10 + n%10; [Link](i+" "); if(n%i == 0) return false;
n /= 10; } // isPalindrome: reverse & compare return true;
return orig == rev; • Time: O((r-l)*log n) Space: O(1) • Any divisor > √n has a pair < √n
• Negative numbers are NOT palindromes • Time: O(√n) Space: O(1)
• Time: O(log n) Space: O(1)
4 PRIME NUMBERS IN RANGE (SIEVE)
Logic : Sieve of Eratosthenes 5 CHECK ARMSTRONG NUMBER
6 CHECK PERFECT NUMBER Logic : Sum of each digit^(# digits) == n
Logic : Sum of proper divisors == n boolean[] sieve = new boolean[r+1];
[Link](sieve, true); int k = [Link](n).length();
int sum = 1; sieve[0]=sieve[1]=false; int sum=0, tmp=n;
for(int i=2; i*i<=n; i++) for(int i=2; i*i<=r; i++) while(tmp>0){
if(n%i==0){ if(sieve[i]) int d=tmp%10;
sum+=i; for(int j=i*i;j<=r;j+=i) sum+=[Link](d,k);
if(i!=n/i) sum+=n/i; } sieve[j]=false; tmp/=10; }
return n!=1 && sum==n; • Time: O(n log log n) Space: O(n) return sum==n; // e.g. 153=1^3+5^3+3^3
// e.g. 28: 1+2+4+7+14=28 • Time: O(log n) Space: O(1)
• Time: O(√n) Space: O(1)
7 EVEN OR ODD
Logic : Use Bitwise AND or Modulo 8 POSITIVE OR NEGATIVE NUMBER
9 SUM OF FIRST N NATURAL NUMBERS Logic : Compare with zero
Logic : Formula: n*(n+1)/2 // Modulo method:
if(n % 2 == 0) → Even if(n > 0) → Positive
// Formula (O(1)): else → Odd else if(n < 0) → Negative
long sum = (long)n*(n+1)/2; // Bitwise method (faster): else → Zero
// Iterative (O(n)): if((n & 1) == 0) → Even // Bitwise trick: (n>>31)&1
long sum=0; • Bitwise AND with 1 checks last bit // gives MSB (sign bit)
for(int i=1;i<=n;i++) sum+=i; • Time: O(1) Space: O(1) • Time: O(1) Space: O(1)
• Formula avoids overflow with long cast
• Time: O(1) with formula

DSA Java Cheat Sheet | Page 4 of 11

✦ DSA CHEAT SHEET (JAVA) – NUMBERS (Part 2) ✦
Page 5

10 SUM OF AP SERIES 11 SUM OF GP SERIES 12 GREATEST OF TWO NUMBERS

Logic : Sn = n/2 * (2a + (n-1)*d) Logic : Sn = a*(r^n - 1)/(r - 1) if r != 1 Logic : Use [Link] or ternary operator

// a=first term, d=common diff, n=terms // a=first term, r=common ratio int max = [Link](a, b);
double sum = (n/2.0)*(2*a + (n-1)*d); if(r == 1) sum = a * n; // Or: int max = (a>b) ? a : b;
// Or: Sn = n/2*(first + last) else // Bitwise (no branch):
double sum2 = (n/2.0)*(a + lastTerm); sum = a*([Link](r,n)-1)/(r-1); int diff = a-b;
• Time: O(1) Space: O(1) • Time: O(1) Space: O(1) int max2 = a-(diff&(diff>>31));
• Time: O(1) Space: O(1)

13 GREATEST OF THREE NUMBERS 14 LEAP YEAR CHECK

Logic : Chain [Link] calls Logic : Div by 4, not 100, unless div by 400 15 REVERSE DIGITS OF A NUMBER
Logic : Extract last digit, build reverse
int max = [Link](a, [Link](b, c)); boolean isLeap =
// Or with if-else: (y%4==0 && y%100!=0) int rev = 0;
if(a>=b && a>=c) max=a; || (y%400==0); while(n != 0) {
else if(b>=c) max=b; • 2000 ✓ leap, 1900 ✗ not leap, 2024 ✓ leap rev = rev*10 + n%10;
else max=c; • Time: O(1) Space: O(1) n /= 10; }
• Time: O(1) Space: O(1) • rev*10 shifts left, n%10 appends digit
• Time: O(log n) Space: O(1)
16 MAX & MIN DIGIT IN NUMBER
17 PRINT FIBONACCI UP TO N TERMS Logic : Extract each digit, track max/min
Logic : F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1 18 FACTORIAL OF A NUMBER
int maxD=0, minD=9; Logic : n! = n*(n-1)*(n-2)*...*1
int a=0, b=1; while(n > 0) {
for(int i=0; i<n; i++){ int d = n % 10; // Iterative:
[Link](a+" "); maxD = [Link](maxD, d); long fact=1;
int tmp = a+b; minD = [Link](minD, d); for(int i=2;i<=n;i++) fact*=i;
a=b; b=tmp; } n /= 10; } // Recursive:
• 0 1 1 2 3 5 8 13 21 ... • Time: O(log n) Space: O(1) long fact(int n){
• Time: O(n) Space: O(1) return n<=1?1:n*fact(n-1); }
• Use BigInteger for n > 20
• Iterative: O(n) Recursive: O(n) stack

DSA Java Cheat Sheet | Page 5 of 11

✦ DSA CHEAT SHEET (JAVA) – NUMBERS (Part 3) ✦
Page 6

19 POWER OF A NUMBER (FAST EXP) 20 FACTORS OF A GIVEN NUMBER 21 ALL PRIME FACTORS OF NUMBER
Logic : Binary Exponentiation: O(log n) Logic : Factors occur in pairs around √n Logic : Divide out each prime factor

long power(long base, long exp) { for(int i=1; i*i<=n; i++){ for(int i=2; i*i<=n; i++){
long res=1; if(n%i==0){ while(n%i==0){
while(exp>0){ [Link](i+" "); print(i);
if((exp&1)==1) res*=base; if(i!=n/i) n/=i; } }
base*=base; [Link](n/i+" "); if(n>1) print(n); // remaining prime
exp>>=1; } } } • At most one prime factor > √n
return res; } • Pairs: (i, n/i). Don't double-count √n • Time: O(√n) Space: O(1)
• Halve exp each step → O(log exp) • Time: O(√n) Space: O(1)
• Time: O(log n) Space: O(1)
22 CHECK STRONG NUMBER
23 CHECK AUTOMORPHIC NUMBER Logic : Sum of factorial of digits == n
24 GCD OF TWO NUMBERS Logic : n^2 ends with n
Logic : Euclidean Algorithm: gcd(a,b)=gcd(b,a%b) int sum=0, tmp=n;
long sq = (long)n*n; while(tmp>0){
int gcd(int a, int b){ long tmp = n; sum += factorial(tmp%10);
while(b!=0){ while(tmp>0){ tmp/=10; }
int tmp=b; sq/=10; tmp/=10; } return sum==n;
b=a%b; a=tmp; } // Alternative: check suffix // e.g. 145: 1!+4!+5!=1+24+120=145
return a; } String s=[Link](n); • Time: O(log n) Space: O(1)
// Base case: gcd(a,0)=a return [Link]((long)n*n).endsWith(s);

• Time: O(log min(a,b)) Space: O(1) • e.g. 5: 5^2=25, ends with 5 ✓

• Time: O(log n) Space: O(1) 25 LCM OF TWO NUMBERS
Logic : LCM = (a*b) / GCD(a,b)
26 CHECK HARSHAD (NIVEN) NUMBER
Logic : n divisible by sum of its digits 27 CHECK ABUNDANT NUMBER long lcm(long a, long b){
Logic : Sum of proper divisors > n return a / gcd(a,b) * b;
int tmp=n, sum=0; // Divide first to avoid overflow
while(tmp>0){ int sum=1; }
sum+=tmp%10; tmp/=10; } for(int i=2;i*i<=n;i++) • Divide before multiply to avoid overflow
return n%sum==0; if(n%i==0){ • Time: O(log min(a,b)) Space: O(1)
// e.g. 18: 1+8=9, 18%9=0 ✓ sum+=i;
• Time: O(log n) Space: O(1) if(i!=n/i) sum+=n/i; }
return sum>n; // e.g.12:1+2+3+4+6=16>12
• Time: O(√n) Space: O(1)

DSA Java Cheat Sheet | Page 6 of 11

✦ DSA CHEAT SHEET (JAVA) – NUMBERS (Part 4) & NUMBER SYSTEM ✦
Page 7

28 SUM OF DIGITS OF A NUMBER 29 SUM OF NUMBERS IN RANGE 30 N PEOPLE, R SEATS (PERMUTATION)

Logic : Extract and accumulate each digit Logic : Sum(1..r) - Sum(1..l-1) Logic : P(n,r) = n! / (n-r)!

int sum = 0; // Sum 1 to n: n*(n+1)/2 long P(int n, int r){

while(n > 0){ long rangeSum(long l, long r){ long res=1;
sum += n % 10; return r*(r+1)/2 - (l-1)*l/2; for(int i=0;i<r;i++)
n /= 10; } } res*=(n-i);
• Digital root: repeat until single digit • Time: O(1) Space: O(1) return res; }
• Time: O(log n) Space: O(1) // e.g. P(5,2)=5*4=20
• Time: O(r) Space: O(1)
31 ADD TWO FRACTIONS
32 REPLACE ALL 0S WITH 1S Logic : a/b + c/d = (a*d + b*c) / (b*d)
Logic : String replace or digit-by-digit 33 SUM OF TWO PRIMES (GOLDBACH)
int num = a*d + b*c; Logic : Try each prime p; check if n-p is prime
// String approach: int den = b*d;
String s = [Link](n); int g = gcd([Link](num),den); for(int p=2; p<=n/2; p++){
s = [Link]('0','1'); // Simplified: num/g , den/g if(isPrime(p) && isPrime(n-p)){
int result = [Link](s); • Always simplify using GCD print(p+"+"+(n-p));
• Time: O(log n) Space: O(log n) • Time: O(log n) Space: O(1) break; } }
• Works for even n ≥ 4 (Goldbach
conjecture)
35 ROOTS OF QUADRATIC EQUATION 1 BINARY TO DECIMAL • Time: O(n√n) Space: O(1)
Logic : x = (-b ± √(b²-4ac)) / 2a Logic : Multiply each bit by 2^position

double disc = b*b - 4*a*c; int dec=0, base=1; 2 BINARY TO OCTAL

if(disc>0){ while(bin>0){ Logic : Group binary digits in 3s from right
double r1=(-b+[Link](disc))/(2*a); dec+=(bin%10)*base;
double r2=(-[Link](disc))/(2*a); bin/=10; base*=2; } // Via decimal:
}else if(disc==0) // Or: [Link]("1011",2) int dec = [Link](bin,2);
double r=-b/(2.0*a); // one root • 1011■ = 8+2+1 = 11■■ String oct = [Link](dec);
else // complex roots • Time: O(n digits) Space: O(1) // Direct: group 3 bits = 1 octal digit

• disc > 0: two real, = 0: one, < 0: // 110 101 → 6 5 → 65■

complex • Each group of 3 bits → 1 octal digit

DSA Java Cheat Sheet | Page 7 of 11

✦ DSA CHEAT SHEET (JAVA) – NUMBER SYSTEM & SORTING & STRINGS (Part 1) ✦
Page 8

3 DECIMAL TO BINARY 4 DECIMAL TO OCTAL 5 OCTAL TO BINARY

Logic : Repeated division by 2, collect remainders Logic : Repeated division by 8 Logic : Each octal digit → 3 binary digits

StringBuilder sb = new StringBuilder(); StringBuilder sb = new StringBuilder(); // Via decimal:

while(n>0){ while(n>0){ int dec = [Link](oct,8);
[Link](0, n%2); [Link](0, n%8); String bin = [Link](dec);
n/=2; } n/=8; } // Direct map: 0→000, 1→001,...7→111
// Or: [Link](n) // Or: [Link](n) • e.g. 7■ = 111■, 5■ = 101■
• Read remainders bottom-up • Time: O(log n) Space: O(log n)
• Time: O(log n) Space: O(log n)
6 OCTAL TO DECIMAL
7 Logic :
CONVERT DIGITS/NUMBERS TO WORDS Multiply each digit by 8^position
3 INSERTION SORT ALGORITHM Logic : Map digits to word arrays, handle chunks
Logic : Insert each element into its correct position int dec=0, base=1;
String[] ones={"Zero","One",..."Nine"}; while(oct>0){
for(int i=1;i<n;i++){ String[] teens={"Ten",..."Nineteen"}; dec+=(oct%10)*base;
int key=arr[i], j=i-1; String[] tens={.."Twenty",..."Ninety"}; oct/=10; base*=8; }
while(j>=0 && arr[j]>key){ // Recursively handle: // Or: [Link]("17",8) → 15
arr[j+1]=arr[j]; // billions, millions, thousands, hundreds • 17■ = 1*8+7 = 15■■
j--; } • Handle 0-19 specially (teens group)
arr[j+1]=key; } • Time: O(log n) Space: O(1)
• Best: O(n) | Worst: O(n^2) | Stable ✓ 4 QUICK SORT ALGORITHM
• Best for nearly-sorted arrays Logic : Partition around pivot, recurse on halves
5 MERGE SORT ALGORITHM
Logic : Divide array, sort halves, merge sorted void quickSort(int[]a,int l,int r){

1 CHECK STRING PALINDROME if(l<r){

Logic : Two-pointer from both ends void mergeSort(int[]a,int l,int r){ int p=partition(a,l,r);
if(l<r){ quickSort(a,l,p-1);
int l=0, r=[Link]()-1; int m=(l+r)/2; quickSort(a,p+1,r); } }
while(l<r){ mergeSort(a,l,m); // partition: place pivot correctly,
if([Link](l)!=[Link](r)) mergeSort(a,m+1,r); // all left<pivot, all right>pivot
return false; merge(a,l,m,r); } } • Avg: O(n log n) | Worst: O(n^2) |
l++; r--; } // merge: two-pointer merge into tmp[] In-place
return true; • Always O(n log n) | Stable ✓ | O(n) space
• Time: O(n) Space: O(1)

DSA Java Cheat Sheet | Page 8 of 11

✦ DSA CHEAT SHEET (JAVA) – STRINGS (Part 2) ✦
Page 9

2 COUNT VOWELS, CONSONANTS, SPACES3 ASCII VALUE OF A CHARACTER 4 REMOVE ALL VOWELS FROM STRING
Logic : Classify each character Logic : Cast char to int Logic : Filter out vowel characters

int v=0,con=0,sp=0; char ch = 'A'; s = [Link]("[aeiouAEIOU]","");

for(char c : [Link]()){ int ascii = (int) ch; // → 65 // Or with StringBuilder:
if(c==' ') sp++; // Key values: StringBuilder sb=new StringBuilder();
else if("aeiouAEIOU".indexOf(c)>=0) v++; // 'A'-'Z': 65-90 for(char c:[Link]())
else if([Link](c)) con++; } // 'a'-'z': 97-122 '0'-'9': 48-57 if("aeiouAEIOU".indexOf(c)<0)
• Time: O(n) Space: O(1) • a-A = 32 (case difference) [Link](c);
• Time: O(1) Space: O(1) • Time: O(n) Space: O(n)

5 REMOVE SPACES FROM STRING

Logic : Replace or filter whitespace 7 REVERSE A STRING 6 REMOVE NON-ALPHABET CHARACTERS
Logic : Two-pointer swap or StringBuilder Logic : Keep only a-z, A-Z
// Remove all spaces:
s = [Link]("\\s",""); // StringBuilder (easiest): s = [Link]("[^a-zA-Z]","");
// Remove leading/trailing only: new StringBuilder(s).reverse().toString(); // Or: [Link](c)
s = [Link](); // Two-pointer on char array: StringBuilder sb=new StringBuilder();
// Remove extra spaces: char[]ch=[Link](); for(char c:[Link]())
s = [Link]("\\s+"," ").trim(); int l=0,r=[Link]-1; if([Link](c)) [Link](c);
• \\s matches any whitespace (space, tab, while(l<r){char t=ch[l];ch[l++]=ch[r];ch[r--]=t;} • Time: O(n) Space: O(n)
etc.) • Time: O(n) Space: O(n)

8 REMOVE BRACKETS FROM EXPRESSION

9 SUM OF NUMBERS IN A STRING 10 Logic :
CAPITALIZE FIRST & LAST OF EACH WORD Flip signs when opening bracket is preceded by -
Logic : Extract consecutive digits, parse to int Logic : Split by space, modify each word
// Track sign: + means keep, - means flip
int sum=0; String[] words = [Link](" "); Deque<Integer> signs = new ArrayDeque<>();
String[] parts = [Link]("[^0-9]+"); for(int i=0;i<[Link];i++){ [Link](1); int curr=1;
for(String p : parts) String w = words[i]; for(char c: [Link]()){
if(![Link]()) if([Link]()==1) words[i]=[Link](); if(c=='(') [Link](curr);
sum+=[Link](p); else words[i]= [Link]([Link](0)) else if(c==')') [Link]();
• Split on non-digits → parse each number +[Link](1,[Link]()-1) else if(c=='+') curr=[Link]();
• Time: O(n) Space: O(n) +[Link]([Link]([Link]()-1));} else if(c=='-') curr=-[Link](); }

• Time: O(n) Space: O(n) • Stack tracks effective sign at each

bracket level

DSA Java Cheat Sheet | Page 9 of 11

✦ DSA CHEAT SHEET (JAVA) – STRINGS (Part 3) ✦
Page 10

11 FREQUENCY OF CHARACTERS IN STRING12 FIND NON-REPEATING CHARACTERS 13 CHECK IF TWO STRINGS ARE ANAGRAMS
Logic : int[26] for lowercase, or HashMap Logic : freq array → find chars with count 1 Logic : Sort both strings and compare

int[] freq = new int[256]; // ASCII int[] freq = new int[256]; // Method 1: Sort
for(char c : [Link]()) for(char c:[Link]()) freq[c]++; char[]a=[Link](); [Link](a);
freq[c]++; for(char c:[Link]()) char[]b=[Link](); [Link](b);
// Print non-zero entries: if(freq[c]==1) print(c); return [Link](a,b);
for(int i=0;i<256;i++) // Preserves order of first occurrence // Method 2: freq array
if(freq[i]>0) print((char)i+":"+freq[i]); • Time: O(n) Space: O(1) // freq[c]++ for s1, freq[c]-- for s2

• Time: O(n) Space: O(1) (fixed 256 array) // Anagram if all freq[i]==0

• Freq method: O(n) | Sort method: O(n log

16 MAXIMUM OCCURRING CHARACTER n)
17 Logic :
REMOVE ALL DUPLICATES FROM STRING freq array → find index with max count
Logic : LinkedHashSet or seen boolean array
int[] freq=new int[256]; 18 PRINT ALL DUPLICATES IN STRING
boolean[] seen=new boolean[256]; for(char c:[Link]()) freq[c]++; Logic : freq array → print chars with count > 1
StringBuilder sb=new StringBuilder(); int maxF=0; char res=' ';
for(char c:[Link]()) for(int i=0;i<256;i++) int[] freq=new int[256];

if(!seen[c]){ if(freq[i]>maxF){maxF=freq[i];res=(char)i;} for(char c:[Link]()) freq[c]++;

seen[c]=true; [Link](c); } • Time: O(n) Space: O(1) for(int i=0;i<256;i++)

• Preserves first occurrence order if(freq[i]>1)

• Time: O(n) Space: O(1) print((char)i+" appears "+freq[i]+" times");

19 REMOVE CHARS OF S2 FROM S1 • Time: O(n) Space: O(1)
Logic : HashSet of s2 chars → filter s1
20 CHANGE LETTER TO NEXT ALPHABET
Logic : Increment ASCII, wrap z→a, Z→A Set<Character> rem=new HashSet<>(); 21 FIND LARGEST WORD IN STRING
for(char c:[Link]()) [Link](c); Logic : Split by spaces, find max length word
StringBuilder sb=new StringBuilder(); StringBuilder sb=new StringBuilder();
for(char c:[Link]()){ for(char c:[Link]()) String[] words=[Link]("\\s+");
if(c=='z') [Link]('a'); if() [Link](c); String largest="";
else if(c=='Z') [Link]('A'); • Time: O(n+m) Space: O(m) for(String w:words)
else [Link]((char)(c+1)); } if([Link]()>[Link]())

• Time: O(n) Space: O(n) largest=w;

• Time: O(n) Space: O(n) for split

DSA Java Cheat Sheet | Page 10 of 11

✦ DSA CHEAT SHEET (JAVA) – STRINGS (Part 4) ✦
Page 11

22 SORT CHARACTERS IN A STRING 23 COUNT NUMBER OF WORDS 24 WORD WITH MOST REPEATED LETTERS
Logic : toCharArray → sort → new String Logic : Split on whitespace, count non-empty tokens Logic : For each word: count unique vs total chars

char[] ch = [Link](); // Trim first to avoid empty splits: String best=""; int maxRep=0;

[Link](ch); String trimmed = [Link](); for(String w:[Link](" ")){

String sorted = new String(ch); if([Link]()) return 0; int[]freq=new int[26];

// Preserves case: uppercase before lower String[] words=[Link]("\\s+"); for(char c:[Link]()) freq[c-'a']++;

• Time: O(n log n) Space: O(n) return [Link]; int rep=(int)[Link](freq).filter(x->x>1).count();

• Time: O(n) Space: O(n) if(rep>maxRep){maxRep=rep;best=w;} }

• Time: O(n*m) Space: O(1) per word

25 CHANGE CASE OF EACH CHARACTER
Logic : Toggle case: XOR with 32 (ASCII trick) 26 CONCATENATE ONE STRING TO ANOTHER
Logic : Use StringBuilder for efficiency 27 FIND SUBSTRING & ITS POSITION
StringBuilder sb=new StringBuilder(); Logic : indexOf() or KMP for O(n) search
for(char c:[Link]()){ // Direct (creates new String each time):
if([Link](c)) String result = s1 + s2; // Built-in (uses efficient algorithm):
[Link]([Link](c)); // Efficient (O(1) amortized append): int pos = [Link](sub);
else [Link]([Link](c)); StringBuilder sb=new StringBuilder(s1); if(pos != -1)
} [Link](s2); print("Found at index: "+pos);
// XOR trick: c^=32 (only for letters!) String result = [Link](); // KMP: precompute failure function
• Time: O(n) Space: O(n) • Avoid + in loops → use StringBuilder // then scan in O(n+m)
• Time: O(n+m) Space: O(n+m) • indexOf: O(n*m) worst | KMP: O(n+m)

28 REVERSE WORDS IN A STRING

Logic : Split → reverse array → join

String[] words=[Link]().split("\\s+");
int l=0,r=[Link]-1;
while(l<r){
String tmp=words[l];
words[l++]=words[r];
words[r--]=tmp; }
return [Link](" ",words);
• Time: O(n) Space: O(n)

DSA Java Cheat Sheet | Page 11 of 11