## Wednesday, September 28, 2011

### SRM518

Level 1 Level 2 Level 3
Div 1 Level 1 Level 2 Level 3
Div 2 Level 1 Level 2 Level 3

## Tutorials:

### Solution

The same with the Div2 - 500 pts.

### Solution

pos[i] represents the biggest character's position but smaller than ith element after ith element.

### Source Code:

//Wednesday, September 14, 2011 14:52 CDT
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class LargestSubsequence
{
public String getLargest(String s)
{
int N = s.length();
int[] pos = new int[N];
for (int i = 0; i < N; i++) {
pos[i] = i;
}
int mmax = -1;
char c = 96;
for (int i = 0; i < N; i++) {
if (c < s.charAt(i)) {
mmax = i;
c = s.charAt(i);
}
char ch = 'a';
for (int j = N - 1; j > i; j--) {
if (s.charAt(i) >= s.charAt(j) && ch <= s.charAt(j)) {
pos[i] = j;
ch = s.charAt(j);
}
}
}
for (int i = 0; i < N; i++) {
System.out.print(pos[i]);
System.out.print(", ");
}
System.out.println();
String ret = "";
for (; mmax != pos[mmax];) {
ret += s.charAt(mmax);
mmax = pos[mmax];
}
ret += s.charAt(pos[mmax]);
return ret;
}
}

### Source Code:

//Wednesday, September 14, 2011 14:52 CDT
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class TwiceString
{
public String getShortest(String s)
{
int N = s.length();
String ret = "";
for(int i=0; i<N; i++){
String str = s + s.substring(i, N);
if(str.startsWith(s) && str.endsWith(s))
ret = str;
}
return ret;
}
}