Find the longest Island


  • 2
    P

    Given a sequence of Land and water codes, find the longest island you can build by filling the water in between any two lands. You can fill only sequence of water, but any number of slots in that sequence.

    Example sequence:
    L, W, L, W, W, L, W
    The Longest sequence length is 4 because (Filled water slots are bolded)
    Let's fill water at slot 2 (index 1) so it becomes L,L,L,W,W,L,W. The longest L sequence is length 3
    Let's fill the two continuous water slots 4,5 (index 3,4) so it becomes L,W,L,L,L,L,W. The longest L sequence is length 4
    Let's fill the last water slot. So it becomes L,W,L,W,W,L,L . The longest L sequence now is 2.

    Best answer is O(N).


  • 1
    W

    sad, I can't even understand the question


  • 0
    P

    Updated the problem. Let me know if it is not clear still


  • 0
    W
    def findLongestIsland(A):
        maxlen = 0
        start = 0
        for i in xrange(len(A)):
            if A[i] == 'L':
                maxlen = max(maxlen, i-start+1)
                start = i
        maxlen = max(maxlen, len(A)-start)
        return maxlen
    

  • 0

    @wadhwala
    Did you try this test case
    {"L", "W", "L", "W", "W", "L", "L"}

    The output should be 5 instead of 4.


  • 0
    public static int maxLength(String[] str){
    		 int [] dp = new int[str.length];
    		 dp[0] = 1;
    		 
    		 for(int i=1; i<dp.length; i++){
    			 if(str[i].equals("W")){
    				 dp[i] = str[i-1].equals("L") ? 2 : dp[i-1]+1;
    			 }
    			 else{
    				 dp[i] = dp[i-1] + 1;
    			 }
    		 }
    		 int res = Integer.MIN_VALUE;
    
    		 for(Integer s : dp){
    			 System.out.print(s +" ");
    			 res = Math.max(s, res);
    		 }
    		 return res;
    	}
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		String[] input1 = {"L", "W", "L", "W", "W", "L", "W"};
    		String[] input2 = {"L", "W", "L", "W", "W", "L", "L"};
    		String[] input3 = {"W", "W", "L", "W", "W", "L", "L"};
    		String[] input4 = {"W", "W", "W", "W", "W", "W", "W"};
    		//System.out.print(maxLength(input1));
    //		System.out.print("answer is:" + maxLength(input2));
    		System.out.print("answer is:" + maxLength(input4));
    	}
    

    Let me know if you think if it has some bug ... ;-)


  • 0
    A

    @happygirl said in Find the longest Island:

    {"W", "W", "L", "W", "W", "L", "L"};

    For the test case, {"W", "L", "L", "W", "W", "L", "L"}, your code will give the result as 5 but the result will be 6.
    In this case, after filling the index 3 and 4 , we get {"W", "L", "L", "L", "L", "L", "L"}, hence the answer will be 6.


  • 0
    3

    @anuj.tewari88 I think you should re-read the question.


  • 0
    L

    @happygirl your code seems to be off?

    ["W", "L", "L", "W", "L", "W"] --> replace the middle "W" with "L" gives max island = 4 yet your code returns 3.


  • 1
    L

    I believe this works:

    def longest_island(lst):
    
        last_water_idx = -1
        new_start = -1
        if lst[0] == "W":
            last_water_idx = 0
            new_start = 0
    
        dp = [0 for i in range(len(lst))]
        dp[0] = 1
    
        for i in range(1, len(lst)):
    
            if lst[i] == "W" and lst[i-1] == "L":
    
                new_start = last_water_idx + 1
                last_water_idx = i
                dp[i] = i - new_start + 1
    
            elif lst[i] == "W" and lst[i-1] == "W":
    
                dp[i] = dp[i-1] + 1
                last_water_idx += 1
    
            else:
    
                dp[i] = dp[i-1] + 1
    
        return max(dp)
    

  • 3
    _
    def longestIsland(s):
        start, cur, res = 0, 0, 0
        for i in range(len(s)):
            if s[i] == "L":
                res = max(res, i-start+1)
                if i == 0 or s[i-1] == "W":
                    cur = i
            else:
                start = cur
        res = max(res, len(s)-start)
        return res
    

  • 0
    S
    /*
     The idea is calculate all the substring's possible answers, starting with lengh = 1 and slowly build up to slen. Here the DP[i][j] refer to the longest island if we have a string which is substring from i to j from the original string.
    */
    
    public int maxLength(String[] str){
        int slen = str.length();
        int[][] dp = new int[slen][slen];
        for(int i = 0; i < slen; i++){
            dp[i][i] = str[i].equals("L") ? 1 : 0;
        }
       for (int i = 0; i < slen; i++){
           for (int j = 0; j <  slen; j++){
               if (i == j) continue;
               for (int k = i; k < j; k++){
                   if(k + 1 == j){
                      if(str[j].equals("W") ){
                        dp[i][j] = Math.max(dp[i][j],
                         str[i].equals("W") ? dp[i][k] : dp[i][k] + 1);
                      }
                     else{
                         dp[i][j] = Math.max(dp[i][j], dp[i][k] + 1);
                     }
                  } 
                  else{
                   dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k+1][j];
                  }
            }
         }
       }
       return dp[0][slen - 1];
    }
    
    
    	W	L	L	W	W	L	L
    W	0	1	2	3	4	5	6
    L		1	2	3	4	5	6
    L			1	2	3	4	5
    W				0	0	1	2
    W					0	1	2
    L						1	2
    L							1

  • 0

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.