STRING PROBLEMS – DIFFERENT APPROACHES, COMPLEXITY

& JAVA
Assignment-ready reference • 43 problems • Best approach code included

Note: For the handwritten submission, write the problem statement, approaches, time/space complexity, and the
highlighted best-approach Java code. Complexity is stated for the usual interpretation of each problem.

1. Reverse a String
Different approaches:

• Loop from end to start and build a new string – O(n), O(n).
• Convert to char array and swap from both ends – O(n), O(n).
• Use [Link]() – O(n), O(n).
Best approach: [Link]() is concise and efficient.
Best complexity: Time O(n), Space O(n).
Java code:
static String reverse(String s) {
return new StringBuilder(s).reverse().toString();
}

2. Check whether a String is Palindrome

Different approaches:

• Compare characters from both ends – O(n), O(1).

• Reverse the string and compare – O(n), O(n).
• Recursion with two indices – O(n), O(n) stack.
Best approach: Two pointers uses constant extra space.
Best complexity: Time O(n), Space O(1).
Java code:
static boolean isPalindrome(String s) {
int l = 0, r = [Link]() - 1;
while (l < r) {
if ([Link](l++) != [Link](r--)) return false;
}
return true;
}

3. Find Duplicate Characters in a String

Different approaches:

• Nested loops – O(n²), O(1) extra.

• HashMap frequency count – O(n) average, O(k).
• Frequency array for ASCII – O(n), O(1) fixed space.
Best approach: For standard ASCII, a frequency array is fastest and simple.
Best complexity: Time O(n), Space O(1) fixed alphabet.
Java code:
static void duplicates(String s) {
int[] f = new int[256];
for (char c : [Link]()) f[c]++;
for (int i = 0; i < 256; i++)
if (f[i] > 1) [Link]((char)i + " -> " + f[i]);
}

4. Why Strings are Immutable in Java?

Different approaches:

String Problems Assignment • Java

 • StringBuilder/StringBuffer could be used for mutable text.
• A normal String cannot be changed after creation; operations create a new object.
• Immutability improves string-pool sharing, security, thread-safety and hash-code caching.
Best approach: Example: [Link]("Java") does not change s; it returns a new String.
Best complexity: Not an algorithmic problem; String operations that appear to modify a String create new objects.
Java code:
String s = "Hello";
[Link](" Java");
[Link](s); // Hello

s = [Link](" Java");
[Link](s); // Hello Java

5. Check Whether One String is a Rotation of Another

Different approaches:

• Try every rotation – O(n²).

• Check (s1+s1).contains(s2) – typically linear/near-linear in modern implementations.
• Use KMP on s1+s1 to guarantee O(n).
Best approach: Length check + KMP gives deterministic O(n).
Best complexity: Time O(n), Space O(n) for LPS/combined string.
Java code:
static boolean rotation(String a, String b) {
if ([Link]() != [Link]()) return false;
return kmpSearch(a + a, b);
}

static boolean kmpSearch(String text, String pat) {

int[] lps = lps(pat);
int i = 0, j = 0;
while (i < [Link]()) {
if ([Link](i) == [Link](j)) { i++; j++; }
if (j == [Link]()) return true;
else if (i < [Link]() && [Link](i) != [Link](j))
j = (j == 0) ? 0 : lps[j - 1];
}
return [Link]();
}

static int[] lps(String p) {

int[] a = new int[[Link]()];
for (int i=1, len=0; i<[Link]();) {
if ([Link](i)==[Link](len)) a[i++]=++len;
else if (len>0) len=a[len-1];
else a[i++]=0;
}
return a;
}

6. Check Whether a String is a Valid Shuffle of Two Strings

Different approaches:

• Generate all interleavings recursively – O(2^(m+n)).

• Sort the combined characters and compare frequencies – O((m+n)log(m+n)), but this alone does not prove order.
• Dynamic programming: dp[i][j] means first i chars of A and first j chars of B can form prefix of C – O(mn).
Best approach: DP correctly preserves the order of both input strings.
Best complexity: Time O(mn), Space O(mn).
Java code:
static boolean validShuffle(String a, String b, String c) {
int m=[Link](), n=[Link]();
if (m+n != [Link]()) return false;
boolean[][] dp = new boolean[m+1][n+1];
dp[0][0] = true;
for (int i=0;i<=m;i++)
String Problems Assignment • Java
 for (int j=0;j<=n;j++) {
int k=i+j;
if (i>0 && dp[i-1][j] && [Link](i-1)==[Link](k-1)) dp[i][j]=true;
if (j>0 && dp[i][j-1] && [Link](j-1)==[Link](k-1)) dp[i][j]=true;
}
return dp[m][n];
}

7. Count and Say Problem

Different approaches:

• Build each next term by scanning the previous term – O(L) per generated term.
• Recursive construction is the same idea but adds call-stack space.
• Run-length encoding of the previous term is the standard best approach.
Best approach: Generate each term using consecutive character counts.
Best complexity: Time O(total generated characters), Space O(term length).
Java code:
static String countAndSay(int n) {
String s = "1";
for (int t=1; t<n; t++) {
StringBuilder out = new StringBuilder();
for (int i=0; i<[Link]();) {
int j=i;
while (j<[Link]() && [Link](j)==[Link](i)) j++;
[Link](j-i).append([Link](i));
i=j;
}
s=[Link]();
}
return s;
}

8. Longest Palindromic Substring

Different approaches:

• Check every substring – O(n³).

• DP table – O(n²) time and O(n²) space.
• Expand around every center – O(n²), O(1).
• Manacher's algorithm – O(n), O(n).
Best approach: Manacher gives the best asymptotic time.
Best complexity: Time O(n), Space O(n).
Java code:
static String longestPalindrome(String s) {
if ([Link]()<2) return s;
String t = "^#" + [Link]("#", [Link]("")) + "#$";
int[] p = new int[[Link]()];
int center=0,right=0,best=0,bestCenter=0;
for(int i=1;i<[Link]()-1;i++){
int mir=2*center-i;
if(i<right) p[i]=[Link](right-i,p[mir]);
while([Link](i+1+p[i])==[Link](i-1-p[i])) p[i]++;
if(i+p[i]>right){ center=i; right=i+p[i]; }
if(p[i]>best){ best=p[i]; bestCenter=i; }
}
int start=(bestCenter-best)/2;
return [Link](start,start+best);
}

9. Longest Recurring (Repeating) Subsequence

Different approaches:

• Recursion – exponential.
• Memoization – O(n²), O(n²).
String Problems Assignment • Java
 • LCS(s, s) while preventing i==j – O(n²), O(n²).
Best approach: Use the LCS DP idea with different indices.
Best complexity: Time O(n²), Space O(n²).
Java code:
static int longestRepeatingSubseq(String s) {
int n=[Link]();
int[][] dp=new int[n+1][n+1];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if([Link](i-1)==[Link](j-1) && i!=j)
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=[Link](dp[i-1][j],dp[i][j-1]);
return dp[n][n];
}

10. Print All Subsequences of a String

Different approaches:

• At each character choose include/exclude – O(2^n).

• Bitmask enumeration – O(n·2^n).
• Backtracking – O(n·2^n) including output cost.
Best approach: Backtracking is easy to understand and naturally prints each subsequence.
Best complexity: Time O(n·2^n), Space O(n).
Java code:
static void subsequences(String s) {
sub(s, 0, new StringBuilder());
}
static void sub(String s, int i, StringBuilder cur) {
if(i==[Link]()){ [Link](cur); return; }
sub(s,i+1,cur);
[Link]([Link](i));
sub(s,i+1,cur);
[Link]([Link]()-1);
}

String Problems Assignment • Java

11. Print All Permutations of a String
Different approaches:

• Use library permutations/iterative insertion – expensive copying.

• Recursion with swapping – O(n·n!) time, O(n) recursion.
• Backtracking with a used[] array – O(n·n!), O(n).
Best approach: Swap-based backtracking avoids creating many temporary arrays.
Best complexity: Time O(n·n!), Space O(n).
Java code:
static void permutations(String s) {
char[] a=[Link]();
perm(a,0);
}
static void perm(char[] a,int idx){
if(idx==[Link]){ [Link](new String(a)); return; }
for(int i=idx;i<[Link];i++){
char t=a[idx]; a[idx]=a[i]; a[i]=t;
perm(a,idx+1);
t=a[idx]; a[idx]=a[i]; a[i]=t;
}
}

12. Split Binary String into Maximum Substrings with Equal 0s and 1s
Different approaches:

• Try all split positions – O(n²).

• Count total zeros/ones first, then scan – O(n).
• Maintain balance: +1 for 1 and -1 for 0; every zero balance gives a valid split.
Best approach: One pass with balance is optimal.
Best complexity: Time O(n), Space O(1).
Java code:
static int maxBalancedSplits(String s) {
int balance=0, count=0;
for(char c:[Link]()){
balance += (c=='1') ? 1 : -1;
if(balance==0) count++;
}
return count;
}

13. Word Wrap Problem

Different approaches:

• Greedy filling each line – O(n), but can be non-optimal.

• Recursive partitioning – exponential.
• DP over possible line endings – O(n²), O(n).
Best approach: DP minimizes the total extra-space cost.
Best complexity: Time O(n²), Space O(n).
Java code:
static int wordWrap(int[] w, int width) {
int n=[Link], INF=1_000_000_000;
int[] dp=new int[n+1];
[Link](dp,INF);
dp[0]=0;
for(int i=1;i<=n;i++){
int len=0;
for(int j=i;j>=1;j--){
len += w[j-1] + (j==i?0:1);
if(len>width) break;
int cost=(i==n)?0:(width-len)*(width-len);

String Problems Assignment • Java

 dp[i]=[Link](dp[i],dp[j-1]+cost);
}
}
return dp[n];
}

14. Edit Distance

Different approaches:

• Recursive insert/delete/replace – exponential.

• Memoized recursion – O(mn), O(mn).
• Bottom-up DP – O(mn), O(mn), reducible to O(min(m,n)) space.
Best approach: Use one-dimensional DP for O(mn) time and O(min(m,n)) space.
Best complexity: Time O(mn), Space O(min(m,n)).
Java code:
static int editDistance(String a,String b){
if([Link]()<[Link]()){ String t=a;a=b;b=t; }
int m=[Link](), n=[Link]();
int[] dp=new int[n+1];
for(int j=0;j<=n;j++) dp[j]=j;
for(int i=1;i<=m;i++){
int prev=dp[0]; dp[0]=i;
for(int j=1;j<=n;j++){
int old=dp[j];
if([Link](i-1)==[Link](j-1)) dp[j]=prev;
else dp[j]=1+[Link](prev,[Link](dp[j],dp[j-1]));
prev=old;
}
}
return dp[n];
}

15. Find Next Greater Number with Same Set of Digits

Different approaches:

• Generate permutations and choose the next one – O(n!).

• Sort/search candidate digits – more complex.
• Next permutation: find pivot, swap with next larger digit, reverse suffix – O(n).
Best approach: The next-permutation algorithm is optimal.
Best complexity: Time O(n), Space O(n) for the char array.
Java code:
static String nextGreater(String s){
char[] a=[Link]();
int i=[Link]-2;
while(i>=0 && a[i]>=a[i+1]) i--;
if(i<0) return "-1";
int j=[Link]-1;
while(a[j]<=a[i]) j--;
char t=a[i];a[i]=a[j];a[j]=t;
for(int l=i+1,r=[Link]-1;l<r;l++,r--){
t=a[l];a[l]=a[r];a[r]=t;
}
return new String(a);
}

16. Balanced Parentheses

Different approaches:

• Count only '(' and ')' – O(n), O(1) for a single bracket type.
• Stack – O(n), O(n), supports (), {}, [].
• Repeated replacement – inefficient, O(n²) or worse.
Best approach: For general bracket types, use a stack.
String Problems Assignment • Java
Best complexity: Time O(n), Space O(n).
Java code:
static boolean balanced(String s){
[Link]<Character> st=new [Link]<>();
for(char c:[Link]()){
if(c=='('||c=='{'||c=='[') [Link](c);
else if(c==')'||c=='}'||c==']'){
if([Link]()) return false;
char o=[Link]();
if((c==')'&&o!='(')||(c=='}'&&o!='{')||(c==']'&&o!='['))
return false;
}
}
return [Link]();
}

17. Word Break Problem

Different approaches:

• Try every prefix recursively – exponential.

• Memoized recursion – O(n²) average with hash-set lookups.
• Bottom-up DP – O(n²) time, O(n) space.
Best approach: DP avoids repeated prefix calculations.
Best complexity: Time O(n²) average, Space O(n).
Java code:
static boolean wordBreak(String s, [Link]<String> dict){
boolean[] dp=new boolean[[Link]()+1];
dp[0]=true;
for(int i=1;i<=[Link]();i++)
for(int j=0;j<i;j++)
if(dp[j] && [Link]([Link](j,i))){
dp[i]=true; break;
}
return dp[[Link]()];
}

18. Rabin-Karp Algorithm

Different approaches:

• Naive pattern matching – O(nm).

• Rabin-Karp rolling hash – expected O(n+m), worst O(nm) because of collisions.
• Use a double hash to reduce collision probability.
Best approach: Rolling hash avoids rechecking most windows.
Best complexity: Expected O(n+m), worst O(nm).
Java code:
static int rabinKarp(String text,String pat){
int n=[Link](),m=[Link]();
if(m>n) return -1;
long base=256, mod=1_000_000_007L, ph=0, th=0, high=1;
for(int i=0;i<m-1;i++) high=high*base%mod;
for(int i=0;i<m;i++){
ph=(ph*base+[Link](i))%mod;
th=(th*base+[Link](i))%mod;
}
for(int i=0;i<=n-m;i++){
if(ph==th && [Link](i,pat,0,m)) return i;
if(i<n-m){
th=([Link](i)*high)%mod;
if(th<0) th+=mod;
th=(th*base+[Link](i+m))%mod;
}
}
return -1;
}

String Problems Assignment • Java

19. KMP Algorithm
Different approaches:

• Naive matching – O(nm).

• Build LPS (longest prefix-suffix) array – O(m).
• KMP search – O(n), total O(n+m).
Best approach: KMP is deterministic linear time.
Best complexity: Time O(n+m), Space O(m).
Java code:
static int kmp(String text,String pat){
if([Link]()) return 0;
int[] lps=new int[[Link]()];
for(int i=1,len=0;i<[Link]();){
if([Link](i)==[Link](len)) lps[i++]=++len;
else if(len>0) len=lps[len-1];
else lps[i++]=0;
}
for(int i=0,j=0;i<[Link]();){
if([Link](i)==[Link](j)){i++;j++;}
if(j==[Link]()) return i-j;
else if(i<[Link]() && [Link](i)!=[Link](j))
j=(j==0)?0:lps[j-1];
}
return -1;
}

20. Convert a Sentence to Mobile Numeric Keypad Sequence

Different approaches:

• Search each character in keypad strings – O(n·k).

• Use a HashMap – O(n) average.
• Use a direct lookup array indexed by character – O(n).
Best approach: Direct lookup gives O(n) time and O(1) fixed space.
Best complexity: Time O(n), Space O(1) fixed mapping.
Java code:
static String keypad(String s){
String[] key={"2","22","222","3","33","333","4","44","444",
"5","55","555","6","66","666","7","77","777","7777",
"8","88","888","9","99","999","9999"};
StringBuilder out=new StringBuilder();
for(char c:[Link]().toCharArray()){
if(c==' ') [Link]('0');
else if(c>='A'&&c<='Z') [Link](key[c-'A']);
}
return [Link]();
}

String Problems Assignment • Java

21. Minimum Bracket Reversals to Balance an Expression
Different approaches:

• Try all reversal combinations – exponential.

• Stack unmatched brackets – O(n), O(n).
• Count unmatched opens/closes directly – O(n), O(1).
Best approach: For only '{' and '}', count unmatched brackets.
Best complexity: Time O(n), Space O(1).
Java code:
static int minReversals(String s){
if(([Link]()&1)==1) return -1;
int open=0, close=0;
for(char c:[Link]()){
if(c=='{') open++;
else if(open>0) open--;
else close++;
}
return (open+1)/2 + (close+1)/2;
}

22. Count All Palindromic Subsequences

Different approaches:

• Generate all subsequences – O(2^n).

• Memoized recursion – O(n²).
• DP where dp[i][j] counts palindromic subsequences in s[i..j] – O(n²).
Best approach: Bottom-up interval DP is standard.
Best complexity: Time O(n²), Space O(n²).
Java code:
static long countPalSubseq(String s){
int n=[Link]();
long[][] dp=new long[n][n];
for(int i=0;i<n;i++) dp[i][i]=1;
for(int len=2;len<=n;len++)
for(int i=0;i+len<=n;i++){
int j=i+len-1;
if([Link](i)==[Link](j))
dp[i][j]=dp[i+1][j]+dp[i][j-1]+1;
else
dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1];
}
return n==0?0:dp[0][n-1];
}

23. Count Occurrences of a String in a 2D Character Array

Different approaches:

• Check every cell and every direction naively – O(R·C·8·L).

• Preprocess pattern with a 2D pattern-search algorithm – more complex.
• For the usual straight-line 8-direction interpretation, scan each cell in 8 directions – O(RCL).
Best approach: The following counts straight-line occurrences in all 8 directions.
Best complexity: Time O(RCL), Space O(1) extra.
Java code:
static int count2D(char[][] g,String w){
int r=[Link],c=g[0].length,L=[Link](),ans=0;
int[] dr={-1,-1,-1,0,0,1,1,1};
int[] dc={-1,0,1,-1,1,-1,0,1};
for(int i=0;i<r;i++) for(int j=0;j<c;j++)
for(int d=0;d<8;d++){
int k=0,x=i,y=j;

String Problems Assignment • Java

 while(k<L && x>=0&&x<r&&y>=0&&y<c&&g[x][y]==[Link](k)){
k++; x+=dr[d]; y+=dc[d];
}
if(k==L) ans++;
}
return ans;
}

24. Search a Word in a 2D Grid of Characters

Different approaches:

• Check straight lines only – O(RCL).

• DFS/backtracking from every matching cell – O(R·C·4^L) for 4 directions.
• Mark visited cells to prevent reuse.
Best approach: Backtracking handles turns in the word path.
Best complexity: Worst O(R·C·4^L), Space O(L).
Java code:
static boolean exist(char[][] g,String w){
for(int r=0;r<[Link];r++)
for(int c=0;c<g[0].length;c++)
if(dfs(g,w,r,c,0)) return true;
return false;
}
static boolean dfs(char[][] g,String w,int r,int c,int k){
if(k==[Link]()) return true;
if(r<0||r>=[Link]||c<0||c>=g[0].length||g[r][c]!=[Link](k)) return false;
char save=g[r][c]; g[r][c]='#';
boolean ok=dfs(g,w,r+1,c,k+1)||dfs(g,w,r-1,c,k+1)
||dfs(g,w,r,c+1,k+1)||dfs(g,w,r,c-1,k+1);
g[r][c]=save;
return ok;
}

25. Boyer-Moore Pattern Searching

Different approaches:

• Naive – O(nm).
• Boyer-Moore bad-character rule – good practical performance; worst O(nm) for the simple bad-character version.
• Full Boyer-Moore adds the good-suffix rule.
Best approach: Use bad-character preprocessing for a compact implementation.
Best complexity: Worst O(nm), practical performance usually much better; Space O(alphabet).
Java code:
static int boyerMoore(String text,String pat){
int n=[Link](),m=[Link]();
if(m==0) return 0;
int[] last=new int[256];
[Link](last,-1);
for(int i=0;i<m;i++) last[[Link](i)]=i;
int s=0;
while(s<=n-m){
int j=m-1;
while(j>=0 && [Link](j)==[Link](s+j)) j--;
if(j<0) return s;
s += [Link](1,j-last[[Link](s+j)]);
}
return -1;
}

26. Convert Roman Numerals to Decimal

Different approaches:

• Repeatedly find symbols and subtract smaller-before-larger – O(n).

• Use a HashMap of Roman values – O(n), O(1).
String Problems Assignment • Java
 • Use a switch/value array – O(n), O(1).
Best approach: Scan from right to left; subtract if current value is smaller than the previous.
Best complexity: Time O(n), Space O(1).
Java code:
static int romanToInt(String s){
int ans=0,prev=0;
for(int i=[Link]()-1;i>=0;i--){
int v=switch([Link](i)){
case 'I'->1; case 'V'->5; case 'X'->10; case 'L'->50;
case 'C'->100; case 'D'->500; case 'M'->1000; default->0;
};
ans += (v<prev)?-v:v;
prev=[Link](prev,v);
}
return ans;
}

27. Longest Common Prefix

Different approaches:

• Compare every pair – O(n·m).

• Sort strings and compare first/last – O(n log n + m).
• Vertical scan all strings character by character – O(total characters) in the worst case.
Best approach: Vertical scan is simple and linear in the inspected input.
Best complexity: Time O(total characters inspected), Space O(1).
Java code:
static String lcp(String[] a){
if([Link]==0) return "";
for(int i=0;i<a[0].length();i++){
char ch=a[0].charAt(i);
for(int j=1;j<[Link];j++)
if(i==a[j].length() || a[j].charAt(i)!=ch)
return a[0].substring(0,i);
}
return a[0];
}

28. Minimum Flips to Make a Binary String Alternating

Different approaches:

• Try both target patterns 0101... and 1010... – O(n), O(1).

• Count mismatches against each pattern – O(n).
• Dynamic programming is unnecessary.
Best approach: One pass counts mismatches for both patterns.
Best complexity: Time O(n), Space O(1).
Java code:
static int minFlipsAlternate(String s){
int f0=0,f1=0;
for(int i=0;i<[Link]();i++){
char a=(i%2==0)?'0':'1';
char b=(i%2==0)?'1':'0';
if([Link](i)!=a) f0++;
if([Link](i)!=b) f1++;
}
return [Link](f0,f1);
}

29. Find the First Repeated Word in a String

Different approaches:

• Compare every pair of words – O(n²).

String Problems Assignment • Java

 • HashSet scan from left to right – O(n) average.
• HashMap can also store frequencies – O(n) average.
Best approach: HashSet finds the first word whose second occurrence is encountered.
Best complexity: Time O(n) average, Space O(k).
Java code:
static String firstRepeated(String s){
[Link]<String> seen=new [Link]<>();
for(String w:[Link]().split("\\s+"))
if() return w;
return null;
}

30. Minimum Number of Swaps for Bracket Balancing

Different approaches:

• Try all swaps – exponential.

• Stack plus explicit swap simulation – O(n), but uses extra space.
• Greedy: whenever a close bracket appears with no available open bracket, swap with a future open bracket;
maintain imbalance – O(n).
Best approach: Greedy gives the minimum number of adjacent-free swaps for a string with equal '[' and ']'.
Best complexity: Time O(n), Space O(n) for the char array.
Java code:
static int minSwapsBrackets(String s){
char[] a=[Link]();
int open=0, swaps=0, balance=0, next=0;
for(int i=0;i<[Link];i++){
if(a[i]=='['){ open++; balance++; }
else balance--;
if(balance<0){
next=i+1;
while(next<[Link] && a[next]!= '[') next++;
if(next==[Link]) return -1;
char t=a[i];a[i]=a[next];a[next]=t;
swaps++;
balance=1;
}
}
return swaps;
}

String Problems Assignment • Java

31. Longest Common Subsequence Between Two Strings
Different approaches:

• Generate subsequences – exponential.

• Memoized recursion – O(mn).
• Bottom-up LCS DP – O(mn), O(mn), reducible to O(min(m,n)) for length only.
Best approach: Use 1D DP when only the LCS length is required.
Best complexity: Time O(mn), Space O(min(m,n)).
Java code:
static int lcs(String a,String b){
if([Link]()<[Link]()){String t=a;a=b;b=t;}
int n=[Link]();
int[] dp=new int[n+1];
for(int i=1;i<=[Link]();i++){
int prev=0;
for(int j=1;j<=n;j++){
int old=dp[j];
if([Link](i-1)==[Link](j-1)) dp[j]=prev+1;
else dp[j]=[Link](dp[j],dp[j-1]);
prev=old;
}
}
return dp[n];
}

32. Generate All Valid IP Addresses from a String

Different approaches:

• Try all 3 split positions – O(1) because an IPv4 address has exactly 4 parts.
• Backtracking over 1–3 digit parts – O(3^n) in a generalized analysis; n is at most 12 for valid IPv4 output.
• Prune parts >255 and leading-zero parts immediately.
Best approach: Backtracking is clean and naturally generates every valid address.
Best complexity: At most 3^n generalized; IPv4 output is bounded, so effectively constant-sized search.
Java code:
static void validIPs(String s){
ipDfs(s,0,0,new StringBuilder());
}
static void ipDfs(String s,int idx,int parts,String cur){
if(parts==4){
if(idx==[Link]()) [Link]([Link](0,[Link]()-1));
return;
}
for(int len=1;len<=3 && idx+len<=[Link]();len++){
if(len>1 && [Link](idx)=='0') break;
String part=[Link](idx,idx+len);
if([Link](part)>255) break;
ipDfs(s,idx+len,parts+1,cur+part+".");
}
}

33. Smallest Window Containing All Distinct Characters of the Same String
Different approaches:

• Check every substring – O(n²) or O(n³).

• Sliding window with a set/frequency array – O(n).
• Two pointers expand until all distinct characters are covered, then shrink.
Best approach: This interpretation makes the problem non-trivial; otherwise a window containing all characters with
multiplicity is the whole string.
Best complexity: Time O(n), Space O(1) fixed alphabet.
Java code:
String Problems Assignment • Java
 static String smallestWindowSelf(String s){
int[] total=new int[256];
int distinct=0;
for(char c:[Link]()) if(total[c]++==0) distinct++;
int[] have=new int[256]; int formed=0,l=0,bestL=0,best=[Link]()+1;
for(int r=0;r<[Link]();r++){
if(have[[Link](r)]++==0) formed++;
while(formed==distinct){
if(r-l+1<best){best=r-l+1;bestL=l;}
if(--have[[Link](l++)]==0) formed--;
}
}
return [Link](bestL,bestL+best);
}

34. Rearrange Characters so No Two Adjacent are Same

Different approaches:

• Backtracking – exponential.
• Sort by frequency and arrange – may require careful feasibility checks.
• Max-heap: repeatedly choose the most frequent character different from the previous one – O(n log k).
Best approach: Max-heap is the standard greedy solution.
Best complexity: Time O(n log k), Space O(k).
Java code:
static String rearrange(String s){
int[] f=new int[256];
for(char c:[Link]()) f[c]++;
[Link]<int[]> pq=(a,b)->b[1]-a[1];
for(int i=0;i<256;i++) if(f[i]>0) [Link](new int[]{i,f[i]});
StringBuilder out=new StringBuilder();
int[] prev=null;
while(![Link]()){
int[] cur=[Link]();
[Link]((char)cur[0]);
if(prev!=null && --prev[1]>0) [Link](prev);
prev=cur;
}
if(prev!=null && prev[1]>1) return "";
return [Link]()==[Link]()?[Link]():"";
}

35. Minimum Characters to Add at Front to Make a String Palindrome

Different approaches:

• Try each prefix/suffix – O(n²).

• Find the longest palindromic prefix using KMP on s + '#' + reverse(s) – O(n).
• Number to add = n - length of the longest palindromic prefix.
Best approach: KMP gives linear time.
Best complexity: Time O(n), Space O(n).
Java code:
static int minAddFront(String s){
String rev=new StringBuilder(s).reverse().toString();
String t=s+"#"+rev;
int[] lps=new int[[Link]()];
for(int i=1,len=0;i<[Link]();){
if([Link](i)==[Link](len)) lps[i++]=++len;
else if(len>0) len=lps[len-1];
else lps[i++]=0;
}
return [Link]()-lps[[Link]()-1];
}

String Problems Assignment • Java

36. Given Words, Print All Anagrams Together
Different approaches:

• Compare every pair – O(n²k).

• Sort every word and use sorted word as a HashMap key – O(n·k log k).
• For lowercase English words, use a 26-frequency signature – O(nk).
Best approach: Frequency signature is linear in total characters for a fixed alphabet.
Best complexity: Time O(total characters), Space O(total characters).
Java code:
static void groupAnagrams(String[] words){
[Link]<String,[Link]<String>> map=new [Link]<>();
for(String w:words){
int[] f=new int[26];
for(char c:[Link]()) f[c-'a']++;
StringBuilder key=new StringBuilder();
for(int x:f) [Link]('#').append(x);
[Link]([Link](),k->new [Link]<>()).add(w);
}
for([Link]<String> g:[Link]()) [Link](g);
}

37. Smallest Window Containing All Characters of Another String

Different approaches:

• Generate all windows – O(n²).

• Sliding window with frequency requirements – O(n+m).
• Expand right until valid, then shrink left while remaining valid.
Best approach: Frequency-array sliding window is optimal.
Best complexity: Time O(n+m), Space O(1) fixed alphabet.
Java code:
static String minWindow(String s,String t){
if([Link]()>[Link]()) return "";
int[] need=new int[256],have=new int[256];
int required=0;
for(char c:[Link]()) if(need[c]++==0) required++;
int formed=0,l=0,bL=0,bLen=Integer.MAX_VALUE;
for(int r=0;r<[Link]();r++){
char c=[Link](r); have[c]++;
if(need[c]>0 && have[c]==need[c]) formed++;
while(formed==required){
if(r-l+1<bLen){bLen=r-l+1;bL=l;}
char x=[Link](l++);
if(need[x]>0 && --have[x]<need[x]) formed--;
}
}
return bLen==Integer.MAX_VALUE?"":[Link](bL,bL+bLen);
}

38. Recursively Remove All Adjacent Duplicates

Different approaches:

• Repeatedly scan and delete groups – O(n²) in the worst case.

• Recursive divide-and-conquer – can also become O(n²).
• Stack/group processing – O(n) time, O(n) space.
Best approach: Remove whole adjacent groups of size >1 and merge groups exposed after deletion.
Best complexity: Time O(n), Space O(n).
Java code:
static String removeDuplicates(String s){
[Link]<Character> chars=new [Link]<>();
[Link]<Integer> cnt=new [Link]<>();
for(int i=0;i<[Link]();){

String Problems Assignment • Java

 int j=i+1;
while(j<[Link]() && [Link](j)==[Link](i)) j++;
char c=[Link](i); int n=j-i;
if(n==1){
if(![Link]() && [Link]()==c){ [Link](); [Link](); }
else { [Link](c); [Link](1); }
}
i=j;
}
StringBuilder out=new StringBuilder();
[Link]<Character> it=[Link]();
while([Link]()) [Link]([Link]());
return [Link]();
}

39. String Matching with Wildcard Characters

Different approaches:

• Recursive matching – exponential.

• 2D DP for pattern/text – O(mn), O(mn).
• 1D DP or greedy backtracking with the last '*' – O(mn) worst case, O(n) extra space.
Best approach: Use 1D DP: '?' matches one character and '*' matches any sequence.
Best complexity: Time O(mn), Space O(n).
Java code:
static boolean wildcard(String s,String p){
int n=[Link]();
boolean[] dp=new boolean[n+1];
dp[0]=true;
for(char pc:[Link]()){
if(pc=='*'){
for(int j=1;j<=n;j++) dp[j]=dp[j]||dp[j-1];
} else {
for(int j=n;j>=1;j--)
dp[j]=(pc=='?'||pc==[Link](j-1)) && dp[j-1];
dp[0]=false;
}
}
return dp[n];
}

40. Number of Customers Who Could Not Get a Computer

Different approaches:

• Simulate using a Set of current users – O(n), O(k).

• Use two-state boolean array: seen customer and currently using computer – O(n), O(1) for a fixed alphabet.
• Count available computers directly.
Best approach: For customer IDs represented by A-Z, a fixed array is simplest.
Best complexity: Time O(n), Space O(1) fixed alphabet.
Java code:
static int unserved(String customers,int computers){
boolean[] seen=new boolean[256], using=new boolean[256];
int free=computers, unserved=0;
for(char c:[Link]()){
if(!seen[c]){
seen[c]=true;
if(free>0){ free--; using[c]=true; }
else unserved++;
} else if(using[c]){
using[c]=false; free++;
}
}
return unserved;
}

String Problems Assignment • Java

41. Transform One String to Another Using Minimum Operations
Different approaches:

• Try all operation sequences – exponential.

• Memoized recursion – O(mn).
• Edit-distance DP with insert, delete and replace – O(mn), O(min(m,n)) space for cost only.
Best approach: This is the standard minimum-edit transformation.
Best complexity: Time O(mn), Space O(min(m,n)).
Java code:
static int minOperations(String a,String b){
return editDistance(a,b);
}

42. Check Whether Two Strings are Isomorphic

Different approaches:

• Try every mapping – O(n²).

• Map each character of s to t with a HashMap and reverse map – O(n).
• Use two fixed arrays for ASCII – O(n), O(1).
Best approach: Two arrays guarantee a one-to-one mapping.
Best complexity: Time O(n), Space O(1) fixed alphabet.
Java code:
static boolean isomorphic(String a,String b){
if([Link]()!=[Link]()) return false;
int[] m1=new int[256],m2=new int[256];
[Link](m1,-1); [Link](m2,-1);
for(int i=0;i<[Link]();i++){
int x=[Link](i), y=[Link](i);
if(m1[x]==-1 && m2[y]==-1){m1[x]=y;m2[y]=x;}
else if(m1[x]!=y || m2[y]!=x) return false;
}
return true;
}

43. Print All Sentences from a List of Word Lists

Different approaches:

• Nested loops work only for a fixed number of word lists.

• Recursive backtracking chooses one word from each list – O(product of list sizes) output.
• If repeated subproblems exist, memoization can avoid recomputing suffixes.
Best approach: Backtracking is the natural solution because every combination must be printed.
Best complexity: Time proportional to the number of sentences printed, plus recursion depth; Space O(number of
lists).
Java code:
static void sentences(String[][] lists){
buildSentences(lists,0,new StringBuilder());
}
static void buildSentences(String[][] a,int row,StringBuilder cur){
if(row==[Link]){[Link]([Link]().trim());return;}
for(String w:a[row]){
int old=[Link]();
[Link](w).append(' ');
buildSentences(a,row+1,cur);
[Link](old);
}
}

String Problems Assignment • Java