String Manipulation Problems in Java

Question

I have the below 2 Problems asked yesterday in an interview

1> Given a string, compute a new string where identical chars that are adjacent in the original string are separated from each other by a "*".

Examples are as shown below::
function name is public String pairStar(String str)

 pairStar("hello") → "hel*lo"     
 pairStar("xxyy") → "x*xy*y"          
 pairStar("aaaa") → "a*a*a*a"

2> Given a string, compute a new string where all the lowercase 'x' chars have been moved to the end of the string.

Examples are as shown below::
function name is public String endX(String str)

endX("xxre") → "rexx"     
endX("xxhixx") → "hixxxx"     
endX("xhixhix") → "hihixxx"

Im not sure how to accomplish the given set of problems, and struggling how to solve this

Uh, are you forgetting some additional constraints? Otherwise this problem seems trivially solveable with a loop and one lookahead symbol (1) or a loop and a counter (2) — Voo
– Voo, Commented Mar 28, 2011 at 14:58
You're not sure - doesn't that mean you don't have the slightest idea? — Ingo
– Ingo, Commented Mar 28, 2011 at 14:59
did you try anything? These seem relatively simple problems that do not require any java experience, and just basic programming logic — Bozho
– Bozho, Commented Mar 28, 2011 at 15:00
given this is an interview question, I'd focus more on the algorithm rather than knowledge of Java API — Dan
– Dan, Commented Mar 28, 2011 at 15:03

Mark Peters · Accepted Answer · 2011-03-28 15:10:33Z

8

For 1), here's a very straightforward regex way:

  String in = "helllo goodbye";
  String out = in.replaceAll("(.)(?=\\1)", "$1*");
  System.out.println(out);

Prints:

hel*l*lo go*odbye

Explanation:

(.)     //match any one character into group 1
(?=\\1) //positive lookahead for that same character by backreferencing group 1

$1*     //replace that one character with the character followed by *

I might take a crack at 2) later, but I don't like multiple questions wrapped into one.

Edit

Alright since I'm in a regex mood here's 2):

  String in = "xhixhix";
  String out = in;
  while (!out.matches("[^x]*x*")) {
     out = out.replaceAll("x(.*)", "$1x");
  }
  System.out.println(out);

This replaces x(something) with (something)x until all the xs are at the end of the string. I'm sure that there's a better way of doing this one with/than regex though.

edited Mar 28, 2011 at 15:10

answered Mar 28, 2011 at 14:58

Mark Peters

81.3k17 gold badges163 silver badges196 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Voo Over a year ago

Well the second variant is quite inefficient and imho a lot harder to understand compared to a simple for-loop. Wouldn't use a regex in production code for such a problem, but it's always nice to work out those regexes as an intellectual exercise ;)

Mark Peters Over a year ago

@Voo: I agree, I upvoted Brian's answer for that reason. His is much easier to understand for 2). For 1) I don't think you'll get much easier than my solution though.

Brian Roach · Accepted Answer · 2011-03-28 14:58:05Z

8

In the first case you can iterate through the string keeping track of the previous character and comparing it to the current. Use a StringBuilder to build the new String.

In the second, iterate through, using two string builders (one for characters other than x, one for x), combine them at the end.

This is just off the top of my head in 30 seconds, and is the simplest approach. The second thought is that I'd prob use a regular expression, now that I think about it for 10 more seconds :)

answered Mar 28, 2011 at 14:58

Brian Roach

77k12 gold badges140 silver badges164 bronze badges

2 Comments

Stephen C Over a year ago

@Deepak - work it out for yourself. If you can't, perhaps you are not ready to interview for Java jobs. Either way, you will learn more by doing this yourself.

Voo Over a year ago

We know what you meant, but if you can't figure it out with the above description it's probably a better idea to get a simple introduction to programming (or Java).

brent777 · Accepted Answer · 2011-03-28 15:05:00Z

3

Maybe I have misunderstood the question but if not if seems pretty simple. Your method could be something like for number 1:

public String pairStar(String s) {
    StringBuilder answer = new StringBuilder();
    char lastChar = s.charAt(0);
    answer.append(lastChar);

    for (int i = 1; i < s.length(); i++) {
        char currentChar = s.charAt(i);

        if (currentChar == lastChar) {
             answer.append("*");
        }
        answer.append(currentChar);
        lastChar = currentChar;
    }
    return answer.toString();
}

answered Mar 28, 2011 at 15:05

brent777

3,3792 gold badges29 silver badges36 bronze badges

Comments

Victor Parmar · Accepted Answer · 2011-03-28 15:12:54Z

2

for the second one:

Loop through the string copying all the non lowercase x's into a new string while keeping count of the x's. At the end, just add the relevant number of x's to produce the final string.

public String endX(String str)
{
    StringBuilder s = new StringBuilder();
    int x = 0;

    for (int i = 0; i < str.length(); ++i)
    {
        if (str.charAt(i) == 'x')
        {
            ++x;
        }
        else
        {
            s.append(str.charAt(i));
        }
    }

    for (int i = 0; i < x; ++i)
    {
        s.append('x');
    }

    return s.toString();
}

answered Mar 28, 2011 at 15:12

Victor Parmar

5,8196 gold badges37 silver badges37 bronze badges

Comments

Dan · Accepted Answer · 2011-03-28 15:01:31Z

1

for 1 you need a state machine with two states: (a) different from previous and (b) same as previous. starting state is (a). for each letter, you have to check in which state you are, output a character and change state accordingly. for each letter read in state (b), you also output a '*'.

for 2 you need an array in which you can shift elements left, and push at the end. 1. push a monitor token at the end (useful for halting condition) 2. iterate over all letters: when finding an "x", shift all elements left, push the x at the end and count the amount of x's you have seen. 3. stop when seeing the monitor token

answered Mar 28, 2011 at 15:01

Dan

1,15114 silver badges34 bronze badges

Comments

rfeak · Accepted Answer · 2011-03-28 15:02:07Z

1

I usually start problems like this with psuedo code, then move to the actual implementation.

For problem 1, here's how the psuedo code in my head works

for each character in the input string{
 if the previous character is the same{
  append a star to output string
 }
 append the character to the output string
}

For problem 2

for each character in the input string{
  if character is an x{
   increment x counter
  } else {
   append the character to the output string
  }
}
x counter times{
  append x to the output string
}

answered Mar 28, 2011 at 15:02

rfeak

8,23431 silver badges28 bronze badges

Comments

GuruKulki · Accepted Answer · 2011-03-28 15:03:58Z

1

for the first problem :

public class StreamGobbler {

    public static void main(String[] a) {

        String s = "xxyy";

        StringBuffer sb = new StringBuffer(s);

        for(int i=0; i < sb.length()-1; i++) {
            if(sb.charAt(i) == sb.charAt(i+1)) {
                sb.insert(i+1, "*");
                i++;
            }
        }

        System.out.println(sb.toString());
    }
}

prints : x*xy*y

answered Mar 28, 2011 at 15:03

GuruKulki

26.6k55 gold badges149 silver badges206 bronze badges

Comments

Vivart · Accepted Answer · 2011-03-29 06:19:12Z

1

for your first problem

public String pairStar(String str){
        StringBuilder sb = new StringBuilder(str);
        for (int i = 0; i < sb.length()-1; i++) {
            if(sb.charAt(i)==sb.charAt(i+1)){
                sb.insert(++i, '*');
            }
        }
        return sb.toString();
    }

and for your second problem

public String endX(String str){
        StringBuilder sb = new StringBuilder(str);
        int length = sb.length()-1;
        for (int i = 0; i < length; i++) {
            if(sb.charAt(i)=='x'){
                sb.deleteCharAt(i--);
                sb.append('x');
                length--;
            }
        }
        return sb.toString();
    }

answered Mar 29, 2011 at 6:19

Vivart

15.4k6 gold badges39 silver badges77 bronze badges

1 Comment

sactiw Over a year ago

+1 for neat and complete solution. Also, may be instead of appending 'x' everytime it occurs we should just maintain a count of no. of 'x' that occurred in some variable say 'xcount' then build a String of 'x' like: StringBuilder sbX = new StringBuilder(xcount); for (int i = 0; i < xcount; i++) { sbX.append('x'); } And finally append that String of 'x' to actual string like: sb.append(sbX);

ıllıllı lק ıllıllı · Accepted Answer · 2014-05-26 07:17:55Z

public class IdenticalChars {

    /**
     * separates any two same n adjacent characters of any string
     * by a * 
     */
    public static void main(String[] args) {
        StringBuilder sb=new StringBuilder();
        String s="aaabcgghelllloii";
        for(int i=0;i+1<s.length();i++){
            if((s.charAt(i)!=s.charAt(i+1)&&(i==0))){
                sb.append(s.charAt(i)+" "+s.charAt(i+1));
                //System.out.println(sb.toString());
            }
            else if((s.charAt(i)!=s.charAt(i+1)&&(i>0))){
                sb.append(s.charAt(i+1));
            }
            else if((s.charAt(i)==s.charAt(i+1))&&(i>0)){
                sb.append("*"+s.charAt(i+1));

            }
            else if((s.charAt(i)==s.charAt(i+1))&&(i==0)){
                sb.append(s.charAt(i)+"*"+s.charAt(i+1));
                }
        }

        System.out.println(sb.toString());
    }

}

output::a*a*abcg*ghel*l*l*loi*i

Rob Truxal · Accepted Answer · 2016-12-16 00:28:20Z

0

step 1. Tell them to shove it and then use python instead!

step 2.:

>>> strin = 'thixs ixs xan XArbitrarxy Stxrxing'
>>> xcnt = strin.count('x')
>>> result = ''.join(i for i in strin if i != 'x')
>>> result = result + ('x' * xcnt)
>>> print result
this is an XArbitrary Stringxxxxxx

edited Dec 16, 2016 at 0:28

answered Dec 16, 2016 at 0:22

Rob Truxal

6,5486 gold badges28 silver badges42 bronze badges

Comments

justNate · Accepted Answer · 2020-07-30 15:37:43Z

These can be completed with recursion.

The first one breaks when the str length reaches 0. Otherwise it checks whether the current and next chars are the same and it they are it returns the current char with a "*" string. Else it just grabs the current string and loops back through. 1)

public String pairStar(String str) {
  int i = 0;
  if (str.length() == 0)
    return str;
  else if (str.length()-1 > i && str.charAt(i) == str.charAt(i+1))
    return str.charAt(i) + "*" + pairStar(str.substring(i+1));
  return str.charAt(i) + pairStar(str.substring(i+1));
}

This also breaks when the str length is 0. Otherwise if the str character is a 'x' then loop through while holding a 'x' char in memory. Else grab the current char, and finally place the 'x' in memory at the end.

public String endX(String str) {
  int i = 0;
  if (str.length() == 0)
    return str;
  else if (str.charAt(i) == 'x')
    return endX(str.substring(i+1)) + 'x' ;
  return str.charAt(i) + endX(str.substring(i+1));
}

Aju · Accepted Answer · 2019-11-12 12:20:04Z

-1

Here is one simple answer using recursion :)

public String pairStar(String str) {
     if(str.isEmpty())return ""; // our exit condition for recursion
     String sub1 = str.substring(0,1); // take the first char
     String sub2 = ""; 
     if(str.length()>1)sub2 = str.substring(1,2); // take second char if it it contains at least 2 chars
     if(sub1.equals(sub2)) return sub1+"*"+pairStar(str.substring(1)); //if two chars are equal putting star between
     return sub1 + pairStar(str.substring(1));//else continue as usual 
}

edited Nov 12, 2019 at 12:20

Aju

4,5997 gold badges38 silver badges61 bronze badges

answered Nov 12, 2019 at 10:16

Varad Paralikar

811 silver badge11 bronze badges

Collectives™ on Stack Overflow

String Manipulation Problems in Java

12 Answers 12

Edit

2 Comments

2 Comments

Comments

Comments

Comments

Comments

Comments

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

12 Answers 12

Edit

2 Comments

2 Comments

Comments

Comments

Comments

Comments

Comments

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related