CMPS 134 Fall 2025
Quiz #2 Sample Solution

The purpose of this document is not only to show a sample solution but, more importantly, to give an account of the thinking process that led to that solution. One might say that it is meant to illustrate, via one small example, how a programmer thinks when formulating a solution to a programming problem.

The quiz began by instructing the student to assume the existence of the following method (by which was meant that the student would be well-served to make use of it (i.e., by calling it) in solving the problem). 

/* Returns the position, within string s, of the k-th occurrence of ch.
** If there are fewer than k occurrences of ch within s, the value returned
** is s.length().
** pre: k >= 1
*/
public static int posOfKth(String s, char ch, int k) { ... }

This method is analogous to, indeed very similar to, the indexOfIthField() method that students made use of in a recent programming assignment. Hence, the concept should have been a familiar one.

Now for the two problems and a description of how one programmer went about solving them.

1. Complete the following method: 

/* Returns the string resulting from replacing, by String t, the substring of s 
** in between its k-th and (k+1)-st occurrences of '$'.  If there are k or fewer
** occurrences of '$' within s, the string returned is s.
** pre: k >= 1
*/
public static String replace(String s, int k, String t) { 
   // Code Missing
}

Note: This method solves essentially the same problem as the setIthField() method that students were to have developed for a recent programming assignment. Hence, not only the concept, but also a way to go about solving it, should have been familiar. End of note.

Solution: A good first step in solving this problem is to recognize that the string to be returned by the method —at least in the case that s has more than k occurrences of '$'— is

prefix + t + suffix

where prefix is the prefix of s through the k-th occurrence of '$', suffix is the suffix of s starting at the (k+1)-st occurrence of '$', and t is the formal parameter.

In the case that s has k or fewer occurrences of '$', the return value should be s itself (as is stated directly in the method's specification).

Based upon these observations, we formulate this pseudocode (in which angle brackets indicate portions of code that need to be refined to become "Java-compliant"): 

public static String replace(String s, int k, String t) { 

   if (<s has k or fewer occurrences of '$'>) {
      return s;
   }
   else {
      String prefix = <prefix of s through the k-th occurrence of '$'>;
      String suffix = <suffix of s starting at the (k+1)-st occurrence of '$'>;
      return prefix + t + suffix;
   }
}

Now, how can we obtain the mentioned prefix and suffix of s? Ah, this is where the posOfKth() method can be used as a valuable tool. To obtain the positions within s of the k-th and (k+1)-st occurrences of '$', we make, respectively, the calls posOfKth(s,'$',k) and posOfKth(s,'$',k+1).

The pseudocode assignment statements that place values into variables prefix and suffix can thus be refined to 

int posK = posOfKth(s, '$', k);
String prefix = s.substring(0, posK + 1);
int posKPlus1 = posOfKth(s, '$', k+1);
String suffix = s.substring(posKPlus1);

Note: The reason for the "+ 1" in the first call to substring() is because we want the resultant string to include the k-th occurrence of '$'. End of note.

All that remains is to refine the if-else guard in our pseudocode to obtain legal Java code. Once again, the posOfKth() method comes to the rescue! Observe that its specification says

If there are fewer than k occurrences of ch within s, the value returned is s.length().

The pseudocode if-else guard is

s has k or fewer occurrences of '$'

Of course, this is equivalent to

s has fewer than k+1 occurrences of '$'

It follows that the call posOfKth(s, '$', k+1) will produce s.length() iff s has k or fewer (i.e., fewer than k+1) occurrences of '$'. Thus, the appropriate if-else guard is

posOfKth(s, '$', k+1) == s.length()

Note: The instructor regrets that the specification of the replace() method used the phrase "k or fewer" rather than "fewer than k+1". End of note.

Putting all this together, a solution is as follows: 

public static String replace(String s, int k, String t) { 

   if (posOfKth(s, '$', k+1) == s.length()) {
      return s;   // s has k or fewer occurrences of '$'
   }
   else {
      // Find the positions in s of the k-th and (k+1)-st occurrences of '$'
      int posK = posOfKth(s, '$', k);
      int posKPlus1 = posOfKth(s, '$', k+1);

      // Form the prefix of s through the k-th occurrence of '$' and
      // the suffix of s starting at the (k+1)-st occurrence of '$'.
      String prefix = s.substring(0, posK + 1);
      String suffix = s.substring(posKPlus1);

      // Paste s back together again, but putting t in place of the
      // substring between the k-th and (k+1)-st occurrences of '$'.
      return prefix + t + suffix;
   }
}

2. Complete this method (preferably using a call to replace()): 

/* Returns the string resulting from removing from s the characters in between
** its the k-th and (k+1)-st occurrences of '$'.  If there are k or fewer
** occurrences of '$' within s, the string returned is s.
** pre: k >= 1
*/
public static String remove(String s, int k) { 
   // Missing code
}

Solution: The insight leading to a short and simple solution is that to remove a substring from a string is the same thing as replacing that substring by the empty string. Which is to say that the body of the remove() method could be the single line

return replace(s, k, "");

If this insight was lacking, the same thought processes that led to the solution to Problem 1 would work here as well. The only difference in the resulting code is that the second return statement would be

return prefix + suffix;

(with no t being mentioned) reflecting the fact that the result should omit the substring of s in between the k-th and (k+1)-st occurrences of '$'.