CareerCup

char* remove(char* str)
{
   char* writer=str,*reader=str;
   char lastchar='.';
   while(*reader)
   {
     if(*reader=='/'){
        if(lastseen!='/'){
          *writer++=*reader;
          lastseen=*reader;
        }
        *reader++;
      }
     else{
        *writer++=*reader;
        lastseen=*reader++;
     }	   
   }
   *writer='\0';
   return str;
}

this has to be solved by scripting instead of writing a program. just use a grep and pipeline it to convert it to the desired string.

If you rewrite below code using c-strings you could make space complexity O(1).


/**
	 * Time: O(N)
	 * Space: O(1)
	 */
	public String removeDuplicateSlashes(String str){
		
		if( str == null ){
			throw new IllegalArgumentException("NULL str passed");
		}		
		
		int copyIndexOffset = 0;
		
		// Space: O(N) make array copy
		final char[] arr = str.toCharArray();
		
		boolean previouslySlashFound = false;
		
		for( int i = 0; i < arr.length; i++ ){
			
			if( arr[i] ==  '/' ){
				if( previouslySlashFound ){
					continue;
				}				
				previouslySlashFound = true;
			}
			else {
				previouslySlashFound = false;
			}			
			
			arr[copyIndexOffset++] = arr[i];
		}
		
		// Space: O(N) allocate new array
		return new String(arr, 0, copyIndexOffset);		
	}

I agree with XYZ algorithm...

Would a regex solution consume significant amounts of extra memory?

we can use sed command instead of the program or we can use a shell script which is just of 2 or 3 lines

what about this

public static String shift(String s, int start, int count) {
		StringBuffer sb = new StringBuffer(s);
		int shiftStartIndex = start + count;
		if (shiftStartIndex >= sb.length()) {
			return s;
		}
		while (shiftStartIndex < sb.length()) {
			sb.setCharAt(start, sb.charAt(shiftStartIndex));
			++start;
			++shiftStartIndex;
		}
		sb.setLength(start);
		return sb.toString();
		
	}
	
	public static String removeSlash(String s) {
		if (s == null || s.length() == 0) {
			return s;
		}
		int i = 0;
		while ( i < s.length()) {
			char c = s.charAt(i);
			if (c == '/') {
				int slashIndex = i;
				++i;
				if (i == s.length()) {
					return s;
				}
				while ((c = s.charAt(i)) == '/') {
					++i;
				}
				int numShift = i - slashIndex - 1;
				if (numShift != 0) {
					s = shift(s, slashIndex+1, numShift);
					i = slashIndex + 1;
				}
			} else {
				++i;
			}
		}
		return s;
		
	}

Keep two pointers
One to move forward in Input-String characters and another to rewrite the Input-String. we rewrite only if current read char is not slash, if it's slash then check for previous char's being slash.
Keep a variable to maintain state, possible states - last-char-slash, last-char-not-slash.

Actually according to the question, only minimum no. of elements need to be moved. But the algorithms mentioned above always move the elements to the right of the current duplicate slash, that is wrong.

For ex: /foo//baaaaaaaaaaaar. Here when we encounter the duplicate slash we are moving the string "baaaaaaaaaaaar" to its left, and that is not minimum. Ideally, the string "/foo/" needs to be moved to its right.

Here is an algorithm.

1. First count the total number of non-duplicate elements (non-de-count)
2. Now iterate through the array, whenever we encounter a sequence of duplicate slashes i.e. one or more slashes, calculate the non-duplicate elements to its left and non-duplicate elements to its right. How?
the current index will give the no. of non-duplicate elements to its left and non-de-count-current will give the non-duplicate elements to its right.
3. if(non-de-left <= non-de-right){
shift left characters to the right;
}else{
call removeDuplicates(str, currentStart,end);
shift right characters to the left;
}

here is a very simple O(n) algorithm using O(1) space


void rem_dup(char *a)
{
int n=strlen(a);
int s=0,e=0;

for(int i=0;i<n;++i)
{
if(a[i]=='/')
{
s=i;
while(a[i]=='/' && i<n) ++i;
e=i;
for(int j=s+1;j<e;++j) a[j]='\0';
}
}

int pos=0;
for(int i=0;i<n;++i)
{
if(a[i]!='\0')
{
a[pos]=a[i];
pos+=1;
}
}
a[pos]='\0';
}

here is a very simple O(n) algorithm using O(1) space


void rem_dup(char *a)
{
int n=strlen(a);
int s=0,e=0;

for(int i=0;i<n;++i)
{
if(a[i]=='/')
{
s=i;
while(a[i]=='/' && i<n) ++i;
e=i;
for(int j=s+1;j<e;++j) a[j]='\0';
}
}

int pos=0;
for(int i=0;i<n;++i)
{
if(a[i]!='\0')
{
a[pos]=a[i];
pos+=1;
}
}
a[pos]='\0';
}

void delSlash(char *s)
{
	if (s == NULL)
		return;

	int i = 1;
	int j = 1;
	int len = strlen(s);

	if (len == 0)
		return;

	while(j < len)
	{
		if (s[j] == '/' && s[i-1] == '/')
			j++;
		else
		{
			s[i] = s[j];
			i++;
			j++;
		}
	}
	s[i] = '\0';
}

void RemoveDuplicateSlashes(char * str)
{
    int l = strlen(str);
    int p = 0;
    for(int i=0;i<l;i++)
    {
        if(i+1 < l && str[i] == '/' && str[i+1] == '/')
        {
            p++;
        }
        str[i] = str[p];
        p++;
    }
}