STRING ASSIGNMENT – 43 QUESTIONS

Two approaches + time/space complexity + short best-approach Java code

A4 writing format: For every question write Approach 1, Approach 2, Best Approach, Time & Space Complexity, and the
short Java code.

1. Reverse a String
Approach 1: Loop from end to start and build a new string – O(n), O(n).
Approach 2: Convert to char array and swap from both ends – O(n), O(n).
Best Approach: [Link]() is concise and efficient.
Time & Space: Time O(n), Space O(n).
Short Java Code:
static String reverse(String s) {
return new StringBuilder(s).reverse().toString();
}

2. Check whether a String is Palindrome

Approach 1: Compare characters from both ends – O(n), O(1).
Approach 2: Reverse the string and compare – O(n), O(n).
Best Approach: Two pointers uses constant extra space.
Time & Space: Time O(n), Space O(1).
Short 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

Approach 1: Nested loops – O(n²), O(1) extra.
Approach 2: HashMap frequency count – O(n) average, O(k).
Best Approach: For standard ASCII, a frequency array is fastest and simple.
Time & Space: Time O(n), Space O(1) fixed alphabet.
Short 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?

Approach 1: StringBuilder/StringBuffer could be used for mutable text.
Approach 2: A normal String cannot be changed after creation; operations create a new object.
Best Approach: Example: [Link]("Java") does not change s; it returns a new String.
Time & Space: Not an algorithmic problem; String operations that appear to modify a String create new objects.
Short 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

Approach 1: Try every rotation – O(n²).
Approach 2: Check (s1+s1).contains(s2) – typically linear/near-linear in modern implementations.
Best Approach: Length check + KMP gives deterministic O(n).
Time & Space: Time O(n), Space O(n) for LPS/combined string.
Short Java Code:
static boolean rotation(String a, String b) {
if ([Link]() != [Link]()) return false;
return kmpSearch(a + a, b);
String Assignment – 43 Questions
 }

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

Approach 1: Generate all interleavings recursively – O(2^(m+n)).
Approach 2: Sort the combined characters and compare frequencies – O((m+n)log(m+n)), but this alone does not prove
order.
Best Approach: DP correctly preserves the order of both input strings.
Time & Space: Time O(mn), Space O(mn).
Short 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++)
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

Approach 1: Build each next term by scanning the previous term – O(L) per generated term.
Approach 2: Recursive construction is the same idea but adds call-stack space.
Best Approach: Generate each term using consecutive character counts.
Time & Space: Time O(total generated characters), Space O(term length).
Short 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

Approach 1: Check every substring – O(n³).
Approach 2: DP table – O(n²) time and O(n²) space.
Best Approach: Manacher gives the best asymptotic time.
Time & Space: Time O(n), Space O(n).
Short Java Code:

String Assignment – 43 Questions

 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

Approach 1: Recursion – exponential.
Approach 2: Memoization – O(n²), O(n²).
Best Approach: Use the LCS DP idea with different indices.
Time & Space: Time O(n²), Space O(n²).
Short 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

Approach 1: At each character choose include/exclude – O(2^n).
Approach 2: Bitmask enumeration – O(n·2^n).
Best Approach: Backtracking is easy to understand and naturally prints each subsequence.
Time & Space: Time O(n·2^n), Space O(n).
Short 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);
}

11. Print All Permutations of a String

Approach 1: Use library permutations/iterative insertion – expensive copying.
Approach 2: Recursion with swapping – O(n·n!) time, O(n) recursion.
Best Approach: Swap-based backtracking avoids creating many temporary arrays.
Time & Space: Time O(n·n!), Space O(n).
Short 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
Approach 1: Try all split positions – O(n²).
String Assignment – 43 Questions
Approach 2: Count total zeros/ones first, then scan – O(n).
Best Approach: One pass with balance is optimal.
Time & Space: Time O(n), Space O(1).
Short 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

Approach 1: Greedy filling each line – O(n), but can be non-optimal.
Approach 2: Recursive partitioning – exponential.
Best Approach: DP minimizes the total extra-space cost.
Time & Space: Time O(n²), Space O(n).
Short 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);
dp[i]=[Link](dp[i],dp[j-1]+cost);
}
}
return dp[n];
}

14. Edit Distance

Approach 1: Recursive insert/delete/replace – exponential.
Approach 2: Memoized recursion – O(mn), O(mn).
Best Approach: Use one-dimensional DP for O(mn) time and O(min(m,n)) space.
Time & Space: Time O(mn), Space O(min(m,n)).
Short 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

Approach 1: Generate permutations and choose the next one – O(n!).
Approach 2: Sort/search candidate digits – more complex.
Best Approach: The next-permutation algorithm is optimal.
Time & Space: Time O(n), Space O(n) for the char array.
Short 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--;
String Assignment – 43 Questions
 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

Approach 1: Count only '(' and ')' – O(n), O(1) for a single bracket type.
Approach 2: Stack – O(n), O(n), supports (), {}, [].
Best Approach: For general bracket types, use a stack.
Time & Space: Time O(n), Space O(n).
Short 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

Approach 1: Try every prefix recursively – exponential.
Approach 2: Memoized recursion – O(n²) average with hash-set lookups.
Best Approach: DP avoids repeated prefix calculations.
Time & Space: Time O(n²) average, Space O(n).
Short 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

Approach 1: Naive pattern matching – O(nm).
Approach 2: Rabin-Karp rolling hash – expected O(n+m), worst O(nm) because of collisions.
Best Approach: Rolling hash avoids rechecking most windows.
Time & Space: Expected O(n+m), worst O(nm).
Short 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;
}

19. KMP Algorithm

Approach 1: Naive matching – O(nm).
String Assignment – 43 Questions
Approach 2: Build LPS (longest prefix-suffix) array – O(m).
Best Approach: KMP is deterministic linear time.
Time & Space: Time O(n+m), Space O(m).
Short 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

Approach 1: Search each character in keypad strings – O(n·k).
Approach 2: Use a HashMap – O(n) average.
Best Approach: Direct lookup gives O(n) time and O(1) fixed space.
Time & Space: Time O(n), Space O(1) fixed mapping.
Short 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]();
}

21. Minimum Bracket Reversals to Balance an Expression

Approach 1: Try all reversal combinations – exponential.
Approach 2: Stack unmatched brackets – O(n), O(n).
Best Approach: For only '{' and '}', count unmatched brackets.
Time & Space: Time O(n), Space O(1).
Short 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

Approach 1: Generate all subsequences – O(2^n).
Approach 2: Memoized recursion – O(n²).
Best Approach: Bottom-up interval DP is standard.
Time & Space: Time O(n²), Space O(n²).
Short 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
String Assignment – 43 Questions
 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

Approach 1: Check every cell and every direction naively – O(R·C·8·L).
Approach 2: Preprocess pattern with a 2D pattern-search algorithm – more complex.
Best Approach: The following counts straight-line occurrences in all 8 directions.
Time & Space: Time O(RCL), Space O(1) extra.
Short 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;
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

Approach 1: Check straight lines only – O(RCL).
Approach 2: DFS/backtracking from every matching cell – O(R·C·4^L) for 4 directions.
Best Approach: Backtracking handles turns in the word path.
Time & Space: Worst O(R·C·4^L), Space O(L).
Short 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

Approach 1: Naive – O(nm).
Approach 2: Boyer-Moore bad-character rule – good practical performance; worst O(nm) for the simple bad-character
version.
Best Approach: Use bad-character preprocessing for a compact implementation.
Time & Space: Worst O(nm), practical performance usually much better; Space O(alphabet).
Short 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;
}

String Assignment – 43 Questions

26. Convert Roman Numerals to Decimal
Approach 1: Repeatedly find symbols and subtract smaller-before-larger – O(n).
Approach 2: Use a HashMap of Roman values – O(n), O(1).
Best Approach: Scan from right to left; subtract if current value is smaller than the previous.
Time & Space: Time O(n), Space O(1).
Short 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

Approach 1: Compare every pair – O(n·m).
Approach 2: Sort strings and compare first/last – O(n log n + m).
Best Approach: Vertical scan is simple and linear in the inspected input.
Time & Space: Time O(total characters inspected), Space O(1).
Short 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

Approach 1: Try both target patterns 0101... and 1010... – O(n), O(1).
Approach 2: Count mismatches against each pattern – O(n).
Best Approach: One pass counts mismatches for both patterns.
Time & Space: Time O(n), Space O(1).
Short 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

Approach 1: Compare every pair of words – O(n²).
Approach 2: HashSet scan from left to right – O(n) average.
Best Approach: HashSet finds the first word whose second occurrence is encountered.
Time & Space: Time O(n) average, Space O(k).
Short 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

Approach 1: Try all swaps – exponential.
Approach 2: Stack plus explicit swap simulation – O(n), but uses extra space.
String Assignment – 43 Questions
Best Approach: Greedy gives the minimum number of adjacent-free swaps for a string with equal '[' and ']'.
Time & Space: Time O(n), Space O(n) for the char array.
Short 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;
}

31. Longest Common Subsequence Between Two Strings

Approach 1: Generate subsequences – exponential.
Approach 2: Memoized recursion – O(mn).
Best Approach: Use 1D DP when only the LCS length is required.
Time & Space: Time O(mn), Space O(min(m,n)).
Short 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

Approach 1: Try all 3 split positions – O(1) because an IPv4 address has exactly 4 parts.
Approach 2: Backtracking over 1–3 digit parts – O(3^n) in a generalized analysis; n is at most 12 for valid IPv4 output.
Best Approach: Backtracking is clean and naturally generates every valid address.
Time & Space: At most 3^n generalized; IPv4 output is bounded, so effectively constant-sized search.
Short 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
Approach 1: Check every substring – O(n²) or O(n³).
Approach 2: Sliding window with a set/frequency array – O(n).
Best Approach: This interpretation makes the problem non-trivial; otherwise a window containing all characters with
multiplicity is the whole string.
Time & Space: Time O(n), Space O(1) fixed alphabet.
Short Java Code:
String Assignment – 43 Questions
 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

Approach 1: Backtracking – exponential.
Approach 2: Sort by frequency and arrange – may require careful feasibility checks.
Best Approach: Max-heap is the standard greedy solution.
Time & Space: Time O(n log k), Space O(k).
Short 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

Approach 1: Try each prefix/suffix – O(n²).
Approach 2: Find the longest palindromic prefix using KMP on s + '#' + reverse(s) – O(n).
Best Approach: KMP gives linear time.
Time & Space: Time O(n), Space O(n).
Short 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];
}

36. Given Words, Print All Anagrams Together

Approach 1: Compare every pair – O(n²k).
Approach 2: Sort every word and use sorted word as a HashMap key – O(n·k log k).
Best Approach: Frequency signature is linear in total characters for a fixed alphabet.
Time & Space: Time O(total characters), Space O(total characters).
Short 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);
}

String Assignment – 43 Questions

37. Smallest Window Containing All Characters of Another String
Approach 1: Generate all windows – O(n²).
Approach 2: Sliding window with frequency requirements – O(n+m).
Best Approach: Frequency-array sliding window is optimal.
Time & Space: Time O(n+m), Space O(1) fixed alphabet.
Short 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

Approach 1: Repeatedly scan and delete groups – O(n²) in the worst case.
Approach 2: Recursive divide-and-conquer – can also become O(n²).
Best Approach: Remove whole adjacent groups of size >1 and merge groups exposed after deletion.
Time & Space: Time O(n), Space O(n).
Short Java Code:
static String removeDuplicates(String s){
[Link]<Character> chars=new [Link]<>();
[Link]<Integer> cnt=new [Link]<>();
for(int i=0;i<[Link]();){
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

Approach 1: Recursive matching – exponential.
Approach 2: 2D DP for pattern/text – O(mn), O(mn).
Best Approach: Use 1D DP: '?' matches one character and '*' matches any sequence.
Time & Space: Time O(mn), Space O(n).
Short 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];
}

String Assignment – 43 Questions

40. Number of Customers Who Could Not Get a Computer
Approach 1: Simulate using a Set of current users – O(n), O(k).
Approach 2: Use two-state boolean array: seen customer and currently using computer – O(n), O(1) for a fixed alphabet.
Best Approach: For customer IDs represented by A-Z, a fixed array is simplest.
Time & Space: Time O(n), Space O(1) fixed alphabet.
Short 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;
}

41. Transform One String to Another Using Minimum Operations

Approach 1: Try all operation sequences – exponential.
Approach 2: Memoized recursion – O(mn).
Best Approach: This is the standard minimum-edit transformation.
Time & Space: Time O(mn), Space O(min(m,n)).
Short Java Code:
static int minOperations(String a,String b){
return editDistance(a,b);
}

42. Check Whether Two Strings are Isomorphic

Approach 1: Try every mapping – O(n²).
Approach 2: Map each character of s to t with a HashMap and reverse map – O(n).
Best Approach: Two arrays guarantee a one-to-one mapping.
Time & Space: Time O(n), Space O(1) fixed alphabet.
Short 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

Approach 1: Nested loops work only for a fixed number of word lists.
Approach 2: Recursive backtracking chooses one word from each list – O(product of list sizes) output.
Best Approach: Backtracking is the natural solution because every combination must be printed.
Time & Space: Time proportional to the number of sentences printed, plus recursion depth; Space O(number of lists).
Short 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);
}
}

Run any solution: Put the method inside a class Main and call it from main(). Example:

String Assignment – 43 Questions

public class Main {
public static void main(String[] args) {
[Link](reverse("hello"));
}
}

String Assignment – 43 Questions